C1412 [HAOI2006]均分数据

内存限制:256 MB 时间限制:1000 ms

题目描述

已知 $N$ 个正整数:$A_1$、$A_2$、……、$A_n$。今要将它们分成M组,使得各组数据的数值和最平均,即各组的均方差最小。均方差公式如下:

$\sigma=\sqrt{\frac{\sum_{i=1}^n(x_i - \bar{x})^2}{n}}$

$\bar{x} = \frac{\sum_{i=1}^nx_i}{n}$

其中 $σ$ 为均方差,$\bar{X}$ 是各组数据和的平均值,$x_i$ 为第 $i$ 组数据的数值和。

输入格式

第一行是两个整数,表示 $N,M$ 的值($N$ 是整数个数,$M$ 是要分成的组数)

第二行有 $N$ 个整数,表示 $A_1$、$A_2$、……、$A_n$。整数的范围是 $1-50$。

(同一行的整数间用空格分开)

输出

这一行只包含一个数,表示最小均方差的值(保留小数点后两位数字)。

样例

样例输入 1

6 3 1 2 3 4 5 6

样例输出 1

0.00

提示

对于全部的数据,保证有 $K \le N \le 20,2 \le K \le 6$。