Time Limit: 3000 MS    Memory Limit: 65536 K 


Description

move King要搬家了,他一共要搬n件物品。这n件物品已按照一定的顺序摆放,每一件 都有一个重量ai。每次他都要按顺序连续的搬运出几件物品。每次搬运都要消耗King的 能量。对King来说,每次消耗的能量有一个特殊的计算公式:能量=(物品重量之和)^2+m。 m是king每次必须要消耗的能量。King希望消耗的总能量最小,同时要把n件物品都搬走。 请你计算一下最少要的能量。

Input

多组数据,处理到EOF. 每组数据第一行2个数n,m。接下来n行,每行1个数,分别表示ai。(n<=500000, ai > 0, 0 <= m <= 1000)

Output

输出最少消耗的能量

Sample Input

6 10 3 4 4 5 2 4

Sample Output

146

Source

经典问题