题目描述

AtCoder公司在其线上商店售卖周边商品。

公司目前剩余$N$件商品，其中第$i$件商品（$1\leq i\leq N$）的重量为$W_i$。

高桥计划将这些商品分装成$D$个幸运袋出售。他希望尽可能减小这些幸运袋中商品总重量的方差。

这里的方差定义为：$V=\frac{1}{D}\displaystyle\sum_{i=1}^D (x_i-\bar{x})^2$。其中，$x_1,x_2,\ldots,x_D$ 分别表示每个幸运袋中商品的总重量，$\bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D)$ 是$x_1,x_2,\ldots,x_D$ 的平均值。

请你求出将商品进行最优分配后，幸运袋中商品总重量的最小方差。

注：允许存在空的幸运袋（空袋的总重量定义为$0$），但每件商品必须恰好放入$D$个幸运袋中的一个。

题目约束

• $2 \leq D\leq N\leq 15$
• $1 \leq W_i\leq 10^8$
• 所有输入值均为整数

输入格式

输入数据从标准输入按以下格式给出：

$N$ $D$

$W_1$ $W_2$ $\ldots$ $W_N$

输出格式

输出将商品分配后能得到的最小方差。只要你的输出与真实值的绝对误差或相对误差不超过$10^{-6}$，即视为正确。

样例输入1

5 3
3 5 3 6 3

样例输出1

0.888888888888889

样例解释1

若将第1件和第3件商品放入第一个幸运袋，第2件和第5件商品放入第二个幸运袋，第4件商品放入第三个幸运袋，则三个幸运袋的总重量分别为$6$、$8$、$6$。

此时平均重量为 $\frac{1}{3}(6+8+6)=\frac{20}{3}$， 方差为 $\frac{1}{3}\left\{\left(6-\frac{20}{3}\right)^2+\left(8-\frac{20}{3}\right)^2+\left(6-\frac{20}{3}\right)^2 \right\}=\frac{8}{9}=0.888888\ldots$，这是能得到的最小方差。

请注意，多件商品可能有相同的重量，且每件商品必须被放入其中一个幸运袋。