问题1414--分糖果

1414: 分糖果

时间限制: 1 Sec  内存限制: 128 MB
提交: 38  解决: 12
[提交] [状态] [讨论版] [命题人:]

题目描述

 幼儿园的N个小朋友得到了M颗糖果。

每个小朋友都有一个想要得到的糖果数目,如果没有达到他们的预期,就会不高兴。不高兴的程度可以用一个数值表示,就是他们无法满足的糖果数目的平方。例如,一个小朋友想要得到32颗糖果,而他只得到29颗糖果,那么有3颗糖果无法满足,因此不高兴值为9.

不幸的是,现有的糖果无法满足所有的小朋友,因此,需要你给出一个分配方案,使得不高兴值的总和最小。

输入

 第一行两个整数MN1<=M<=2*10^9)(1<=N<=100,000

接下来N行,每行一个整数,表示每个孩子想要的糖果数。每个小于2*10^9且总和肯定超过M

输出

 最少生气值总和。输出数据保证结果在int64范围之内。

样例输入 Copy

5 3
1
3
2

样例输出 Copy

1

提示

【数据范围】

40%的数据M<=200,000

70%的数据所有小朋友想要的糖果数<=100,000

 【输出输出样例2

candy.in

candy.out

10 4
4
5
2
3

4