Hide

# Problem OCovered Walkway

Your university wants to build a new walkway, and they want at least part of it to be covered. There are certain points which must be covered. It doesnâ€™t matter if other points along the walkway are covered or not.

The building contractor has an interesting pricing scheme. To cover the walkway from a point at $x$ to a point at $y$, they will charge $c + (x-y)^2$, where $c$ is a constant. Note that it is possible for $x=y$. If so, then the contractor would simply charge $c$.

Given the points along the walkway and the constant $c$, what is the minimum cost to cover the walkway?

## Input

Input consists of a single test case. The test case will begin with a line with two integers, $n$ ($1 \le n \le 1\, 000\, 000$) and $c$ ($1 \le c \le 10^{9}$), where $n$ is the number of points which must be covered, and $c$ is the contractorâ€™s constant. Each of the following $n$ lines will contain a single integer, representing a point along the walkway that must be covered. The points will be in order, from smallest to largest. All of the points will be in the range from $1$ to $10^9$, inclusive.

## Output

Output a single integer, representing the minimum cost to cover all of the specified points. All possible inputs yield answers which will fit in a signed $64$-bit integer.

Sample Input 1 Sample Output 1
10 5000
1
23
45
67
101
124
560
789
990
1019

30726

Hide