Problem1490--司令官PIPI II

1490: 司令官PIPI II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 350  Solved: 63
[Submit] [Status] [Web Board] [Creator:]

Description

为了响应国家的号召,司令官PIPI决定在大学里面征集一批同学进入部队。计划开启后,CSU有M位同学参加报名,司令官PIPI想在里面选出N位同学。由于部队对身高有严格要求,PIPI要求这N位同学的身高尽可能接近,即选出的同学身高方差尽可能小,请你帮帮PIPI。
PS:
对于序列x1,x2,...xn,序列方差为:
s2=[(x1-k)2+(x2-k)2+...(xn-k)2]/n
其中k为序列x1,x2,...xn的均值。

Input

输入包含多组测试样例(case≤10)。
对于每组测试样例,第一行输入两个数字M,N,含义如题面所示(0<N≤M≤1e5)。
第二行输入M个数字,ai 代表第i个同学的身高(0<ai≤1e5)。

Output

对于每组测试用例,输出最小方差*N的整数部分(即向下取整)。

Sample Input

5 3
1 2 3 4 5

Sample Output

2

Source/Category