题目描述

\(n\) 个小朋友在花园里玩耍，老师拿出 \(m\) 颗糖果来分发。每个小朋友想要 \(x_i\) 颗糖果， 如果他分到 \(y_i\) 颗糖果，当 \(y_i<x_i\) 时，他就会不高兴，不高兴度为 \((x_i-y_i)×(x_i-y_i)\)。请你来帮助老师来分发糖果，使得全部小朋友的不高兴度之和最小。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为两个正整数 \(m(≤2×10^9)\) 和 \(n(≤10^5)\)；接下来一行为 \(n\) 个正整数，分别表示每个小朋友的需求值 \(x_i，m_i≤∑x_i≤2×10^9\)。

输出格式

对于每组数据，输出所有小朋友的不高兴度之和。

样例1

样例输入1

3
5 3
1 3 2
10 4
4 5 2 3
10 4
3 4 5 5

样例输出1

1
4
13

样例2

样例输入2

3
5 3
1 3 2
10 4
4 5 2 3
10 4
3 4 5 5

样例输出2

1
4
13

样例3

样例输入3

见提示中的 candy3.in。

样例输出3

见提示中的 candy3.ans。

提示

candy3.in

candy3.ans

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("candy.in","r",stdin);
freopen("candy.out","w",stdout);