Chia đoạn tối ưu

Cho dãy số nguyên $a_1,a_2,\dots ,a_n$ và một số nguyên $C$.

Bạn phải chia dãy thành các đoạn con liên tiếp không rỗng. Số đoạn tuỳ ý, miễn là mỗi phần tử thuộc đúng một đoạn và các đoạn phủ kín dãy theo thứ tự từ trái sang phải.

Chi phí của một đoạn bằng hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất trong đoạn đó, cộng thêm $C$. Nói cách khác, đoạn $[l,r]$ có chi phí

$${max}_{l\le i\le r}{a}_i-{min}_{l\le i\le r}{a}_i+C.$$

Hãy tìm tổng chi phí nhỏ nhất của một cách chia.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $C$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le C\le {10}^{12}$
• $1\le a_i\le {10}^{12}$

Ví dụ