样例下载

题目描述

$N$ 个非负整数构成一个数列 $A_1, A_2, ……, A_N$，现在要将其划分成若干段，每段的代价定义为该段内所有数的和的平方再加一个常数 $C$。

划分的总代价为每一段的代价之和。

问：如何划分可以使得总代价最小？你只需要输出这个最小值。

输入格式

多组数据。对于每组数据：

• 第一行：两个整数 $N, C$
• 第二行：$N$ 个整数 $A_i$

输出格式

每组数据的答案占一行，输出一个整数，表示最小的总代价。

样例输入

5 4
1 2 3 0 6

样例输出

66

数据范围

25%的数据，$0 ≤ N ≤ 10$

50%的数据，$0 ≤ N ≤ 1 × 10^3$

100%的数据，不会超过 20 组测试数据，全部满足 $0 ≤ N ≤ 5 × 10^5; 0 ≤ A_i ≤ 200; 0 ≤ C ≤ 1000$。