Description

Professor P is going to watch the Olympics, but he cannot part with his toys, so he decides to ship all his toys to Beijing. He uses his own compressor, which can compress any item into a lump and then place it into a special one-dimensional container.

Professor P has $n$ toys numbered $1 \cdots n$. After compression, the one-dimensional length of the $i$-th toy is $C_i$.

To organize them conveniently, Professor P requires:

• The toy indices in a one-dimensional container must be consecutive.
• Additionally, if a container holds more than one toy, a unit-length filler must be added between any two adjacent toys. Formally, if toys $i$ through $j$ are placed in one container, the container length is $x=j-i+\sum\limits_{k=i}^{j}C_k$.

The manufacturing cost of a container depends on its length. According to the professor’s study, if a container has length $x$, its cost is $(x-L)^2$, where $L$ is a constant. Professor P does not care about the number of containers; he can make containers of any length, even exceeding $L$. He wants the total cost of all containers to be minimized.

Input Format

The first line contains two integers separated by a space, denoting $n$ and $L$.

Lines $2$ to $(n + 1)$ each contain one integer. Line $(i + 1)$ contains the length $C_i$ of the $i$-th toy.

Output Format

Output a single integer on one line, the minimum possible total cost of all containers.

5 4
3
4
2
1
4

1

Hint

For all test points, $1 \leq n \leq 5 \times 10^4$, $1 \leq L \leq 10^7$, $1 \leq C_i \leq 10^7$.

Translated by ChatGPT 5