Migrated from Lutece 2042 命运石之门

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Sakura 已经一周没有来学校了，子辉也明白她或许再也来不了学校了。那晚，在烟花之下，他通过超能力看到了 Sakura 的未来——在病床上不断失去着过去美好的记忆，最终离世。子辉不愿自己心爱的女生独自面对这样的未来，他决定帮她一把。

从前，子辉得到了过一种古代炼金术，可以把一些饼干提炼成魔法石。从而打开通往孤独的观测者的命运石之门。寻找Sakura的记忆碎片，帮Sakura恢复记忆。

现在，子辉有 $x$ 块饼干 ， 这 $x$ 块饼干的体积之和为 $y$ ， 则将这些饼干提炼成一块魔法石得到的魔法石的体积为$( x+y-1-P )^2$，其中 $P$ 为魔法系数。 子辉现在正好有数量为 $n$ 的饼干序列 ， 其中第$i$块饼干的体积为 $a_i$ ，但是由于某种神秘力量，他只能选取一段连续的饼干提炼成魔法石， 而且无法调换饼干的顺序，他想把所有的饼干都用来提炼魔法石，但是不想魔法石的体积和太大，免得房间放不下，请问，最优策略下，魔法石的体积和的最小值是多少。

Input

第一行两个整数 $n$ ( $1 \le n \le 50000$ ), $P$ ($1 \le P \le 10^6$ ) ,分别代表 饼干的数量 和 魔法系数 $P$。 接下来有$n$行 第 $i+1$ 行有 一个正整数 $V_i$ ，代表第i块饼干的体积为 $V_i$ ( $1 \le V_i \le 10^5$ ) 。

Output

一个正整数$ans$，代表把所有饼干提炼成魔法石后，魔法石的最小体积和。

Samples

5 6
3
2
4
1
6

0

Note

样例解释

把第 1 个到第 2 个饼干提炼成一个魔法石， 该魔法石的体积为$( 2 + 5 -1 - 6 )^2 = 0$

把第 3 个到第 4 个饼干提炼成一个魔法石， 该魔法石的体积为$( 2 + 5 -1 - 6 )^2 = 0$

把第 5 个到第 5 个饼干提炼成一个魔法石， 该魔法石的体积为$( 1 + 6 -1 - 6 )^2 = 0$

所以在该方案下，3个魔法石的总体积大小为 0

Resources

2018 UESTC Training for Dynamic Programming