Migrated from Lutece 2061 愿你有一天能和你重要的人重逢

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说了这最后一句话。

窗外樱花飘落，却再无樱花了。

编不动的题面：A现在在玩游戏，他现在有$N$节地铁车厢，这$N$节车厢按顺序排列，长度不一定相同，第$i$节车厢长度为$a_i$。在这个游戏中非常扯淡的是，第$i$节车厢只能连接在第$i-1$节车厢或者机车头后面。为了充分利用已有的$N$个车厢，他决定添加若干个长度为$len$的机车头，将这$N$节车厢分别连接到机车头后面，形成若干个长度不一定相同的列车(列车长度包括机车头的长度与车厢的长度，以及车厢与车厢、车厢与机车头之间的连接处的长度，每个连接的长度为1)。A是个有强迫症的孩子，他总是希望每一列列车的长度都能够尽量接近他心目中的完美列车长度$Perfect$，并且认为如果一列列车长度是$sum$时，会使得他添加$(sum - Perfect) ^ 2$的羞耻度，A希望能够设计一种分配车厢的方法使得他不感到太过于尴尬。请问A的最低尴尬度是多少？

Input

第一行输入三个数字分别是$N$、$len$ 和 $Perfect$，分别代表车厢的数目和机车头的长度和A心目中完美的列车长度。($1 \leq N \leq 10^5, 1 \leq N \leq 10^4 , 1 \leq Perfect \leq 10^6$)

第二行输入 $N$ 个数字， 第 $i$ 个数字表示第 $i$ 节车厢的长度。($1 \leq a_i \leq 10^4$)

Output

输出A的最低的尴尬值。

Samples

3 1 6
1 2 3

1

Note

比如某列列车由一个机车头和三节车厢组成，三节车厢的长度分别为 $a_1,a_2,a_3$，则改造这列列车的羞耻度则是$(len + a[1] + a[2] + a[3] + 3 - Perfect)^2$

Resources

2018 UESTC Training for Dynamic Programming