[HAOI2006]均分数据

题目描述

已知 $n$ 个正整数 $a_1,a_2 ... a_n$ 。今要将它们分成 $m$ 组,使得各组数据的数值和最平均,即各组的均方差最小。均方差公式如下: $$\sigma = \sqrt{\frac 1n \sum\limits_{i=1}^n(\overline x - x_i)^2},\overline x = \frac 1n \sum\limits_{i=1}^n x_i$$ 其中 $\sigma$ 为均方差,$\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

说明

样例解释:$1,6$、$2,5$、$3,4$ 分别为一组 【数据规模】 对于 $40\%$ 的数据,保证有 $m \le n \le 10$,$2 \le m \le 6$ 对于 $100\%$ 的数据,保证有 $m \le n \le 20$,$2 \le m \le 6$