Telephone Line

Jaehyeon wants to install a telephone line through a village.

The village has $N$ utility poles standing in a row; the initial height of the $i$-th pole is $H_i$. Jaehyeon may first raise each pole by any amount (heights can never be lowered), and then runs the telephone line through poles $1, 2, \dots, N$ in order. Let $h_i$ ($h_i \ge H_i$) be the final height of pole $i$ after raising.

• Raising cost: raising a pole by $X$ costs $X^2$. So pole $i$ contributes $(h_i - H_i)^2$.
• Line cost: connecting two adjacent poles $i$ and $i+1$ costs $C \times |h_i - h_{i+1}|$.

Find the minimum total cost to raise the poles and connect the whole line. The total cost is the sum of all raising costs plus the sum of all line costs.

The first line contains the number of poles $N$ and the cost coefficient $C$, separated by a space. ($1 \le N \le 100{,}000$, $1 \le C \le 100$)

Each of the next $N$ lines contains the initial height $H_i$ of one pole. ($1 \le H_i \le 100$)

Print the minimum total cost to connect the entire telephone line on a single line.

Consider $5$ poles with $C = 2$ and initial heights $2, 3, 5, 1, 4$. Raising them to $[3, 3, 5, 3, 4]$ yields a total cost of $15$, and no smaller cost is possible.