Background

士兵的生气指数（angry）

【题目描述】

将军在攻占敌军城堡之前许诺每一位士兵将与他们一起瓜分城堡内的金币，将军的部队里一共有n位士兵，对于第i（1≤i≤n）位士兵，将军许诺他在攻占城堡之后将会给他ai块金币。

后来将军的部队在没有损失一兵一卒的情况下攻占了城堡，并获得了m块金币。但是将军发现这些金币可能是不够分给这些士兵的（也可能够分）。

对于第i位士兵来说，如果分配给他的金币的数量没有达到他的期望ai，这位士兵就会生气，每差一块金币，士兵的生气指数就会增加，可以认为他生气的程度等于他少得到的金币数量的平方。

举个例子，假如有一位叫禾木的士兵，将军之前允诺他会给他35块金币，但是他最终只得到了32块金币，少了3块金币，则他的生气指数是3​^2^​=9。

请你帮助将军设计一种金币的分配方案，使所有士兵的生气指数之和最小。

【输入格式】

输入的第一行包含两个整数m和n，以一个空格分隔，分别表示总金币数和士兵数。

输入的第二行包含n个整数，两两之间以一个空格分隔，依次表示a​~1~​,a​~2~​, …, an。

【输出格式】

一个整数，表示所有士兵生气指数之和的最小值。

【样例1输入】

10 4
4 5 2 3

【样例1输出】

4

【样例1解释】

共10块金币，4位士兵，给每位士兵的金币为允诺他的数量减1，也就是依次给3、4、1、2块金币，这样的话每位士兵都少1块，每位士兵的生气指数都是1​^2^​=1，所有士兵总的生气指数为4×1​^2^​=4，答案4是最优方案。

【样例2输入】

15 4
4 5 2 3

【样例2输出】

0

【样例2解释】

若共有15块金币，4位士兵，则士兵需要的金币总数为4+5+2+3=14块<15块，此时每位士兵都能够得到许诺的金币，这样就没有人会生气。

【样例3】

见选手目录下的angry/angry3.in与angry/angry3.ans（见CCF官方网站）。

【数据范围与提示】

对于20% 的数据，n, ai≤100, m≤10000。

对于40% 的数据，n≤1000。

对于60% 的数据，n≤10000。

对于100% 的数据，1≤n≤10​^6^​, 1≤ai≤10​^6^​, 1≤m≤2×10​^12^​。

【分析】

对于一位少得到a块金币的士兵来说，他的生气指数为a​^2^​，若再给他一枚金币，他的生气指数会变为 (a−1)​^2^​，下降了a​^2^​−(a−1)​^2^​=2a−1，可以发现，将金币优先派发给生气指数大的士兵能够最快地降低整体的生气指数。基于这个规律，我们可以设计一个贪心策略：优先将金币发给少得到金币数量大的士兵。但是由于m最大能达到2×10​^12^​，一个一个派发金币的操作必然超时，所以考虑整体派发金币。

有很多解法可以实现“整体派发金币”的效果，这里采用排序的方法，先将a~1~到an从大到小排序（a​~1~​≥a​~2~​≥…≥an）。然后，我们循环i从1到n，目的是尝试将a~1~ 至 ai 都减小为ai​~+1~​。特别地，当i=n时，我们的目的是尝试将a~1~ 至 an 都减小为0（所以这里可以设存在一个an​~+1~​=0）。当 (ai−ai​~+1~​)×i≤m时，可以将a~1~ 至 ai 都减小为ai​~+1~​，消耗的金币数（m减小的值）为 (ai−ai​~+1~​)×i；否则，说明无法将a~1~ 至 ai全部减小到ai​~+1~​，此时要求使用剩下的m块金币将a~1~ 至ai减小得尽量平均，即其中m%i个数减小m/i+1，另外i−m%i个数减小m/i（此时金币恰好分完）。最终计算每一个ai的平方和即为最小的生气指数之和。

【参考代码】

Limitation

1s, 1024KiB for each test case.