时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定一个整数序列：\(a[1],a[2],…,a[N]\)，现在需要把这 \(N\) 个数按原来的顺序分成 \(K\) 组，每组包含若干连续的项。每组的代价为定义为：\((∑a[i])^2+M\)，其中 \(M\) 为一个常数。

　　那么该如何分组，才能让 \(K\) 组的代价和最小。

【输入格式】

　　第一行是包含两个整数 \(N\) ,\(M\),\(K\)。
　　接下来的 \(N\) 行，每行一个整数，表示 \(a[i]\)。

【输出格式】

　　一个整数，表示最小代价和。

【输入输出样例】

　Input

8 30 3
3
2
5
6
3
1
4
7

　Output

411

【数据限制】

　　对于 \(20\%\) 的数据，\(K ≤ N ≤ 1000\)
　　另有 \(20\%\) 的数据，\(K=2\)
　　对于 \(100\%\) 的数据，\(K ≤ N ≤ 100000\)，\(1 ≤ M ≤ 1000\)，\(1 ≤ a[i] ≤ 100\)

【来源】

　　Mr.he**