[HAOI2006]均分数据

给定 $N$ 个正整数 $A_1,A_2,\ldots,A_N$。现在需要将它们分成 $M$ 个非空组，每个整数恰好属于一个组，且同一组中的元素不要求在原序列中连续。

设第 $i$ 组中所有整数之和为 $x_i$，所有组和的平均值为

$$\bar{x}=\frac{1}{M}\sum_{i=1}^{M}x_i,$$

定义各组和的均方差为

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

请合理分组，使 $\sigma$ 最小。

输入格式

第一行包含两个整数 $N,M$，分别表示整数的数量和需要划分的组数。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，相邻整数之间用空格分隔。

输出格式

输出一个实数，表示最小均方差，保留小数点后两位。

样例输入

6  3
1  2  3  4  5  6

样例输出

0.00

数据范围

• 对于所有数据，$2\le M\le 6$；
• $M\le N\le 20$；
• $1\le A_i\le 50$。

来源与许可

本题为 HAOI 2006 试题「均分数据」，题面与测试数据整理自 BZOJ。

样例 1

输入

6  3
1  2  3  4  5  6

输出

0.00