工作分配

【问题描述】

GG 有 n 份工作要完成，每一份工作有一个类型系数 Ak 。由于工作数目太多了， GG 光靠自己的能力是无法完成的，所以他打算雇佣很多工人来帮他。工人是非常精明的，他们要求按照工作数目收费，如果分派给他的工作数目小于 k ，他们将不愿意接受。工人完成一份工作的收费是 C 。但是， GG 也是很精明的老板，考虑到有些工作之间很类似，完成了一份工作之后可以很轻松的完成下一份工作，所以他提出了这样的要求，假设工人接受的工作的类型系数是 {B1, B2, B3 … Bp} ，他能够得到的报酬将是 C + (maxB – minB)^2 。

作为 GG 的助理，现在你有责任告诉他，为了完成这些工作，他至少要支付多少钱给工人（不算你的工资）？

【输入格式】

第一行三个正整数 n 、 k 、 C （ 1 <= k <= n <= 10^6 ， 0 < C <= 10^9 ），意义如题所述；

第二行 n 个正整数描述 n 份工作的类型系数（ 0 < A <= 10^9 ）。

【输出格式】

一个整数表示 GG 最少需要支付的工资（保证答案不大于 10^17 ）。

【输入样例】

2 1 1
2 4

【输入样例】

2

【样例说明】

如果分给一个工人做，收费为 1 + (4 – 2)^2 = 5 ；

如果分给两个工人作，收费为 1 + 1 = 2 ；

所以最小收费为 2 。

【数据规模】

对于 50 分的测试数据中保证有 N <= 1000

对于 80 分的测试数据中保证有 N <= 100000