幸运袋

题目描述

AtCoder Inc. 在其网上商店销售商品。

公司还剩下 $N$ 件商品。

第 $i$ 件商品 $(1\le i\le N)$ 的重量为 $W_i$。

高桥将把这些商品分成 $D$ 个幸运袋出售。

他希望使各幸运袋中商品总重量的方差最小。

这里,设各幸运袋中商品总重量为 $x_1,x_2,\ldots,x_D$,其平均值为 $\bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D)$,则方差定义为 $V=\frac{1}{D}\displaystyle\sum_{i=1}^D (x_i-\bar{x})^2$。

求出使方差最小时各幸运袋中商品总重量的方差。

允许存在空的幸运袋(此时该袋中商品总重量记为 $0$),

但每件商品必须恰好放入 $D$ 个幸运袋中的一个。

输入格式

输入按以下格式从标准输入给出:

$N$ $D$
$W_1$ $W_2$ $\ldots$ $W_N$

输出格式

输出使方差最小时各幸运袋中商品总重量的方差。

当输出与真实值的绝对误差或相对误差不超过 $10^{-6}$ 时,判定为正确。

样例

5 3
3 5 3 6 3

0.888888888888889

如果将第一件和第三件商品放入第一个幸运袋, 第二件和第五件商品放入第二个幸运袋, 第四件商品放入第三个幸运袋, 则各袋中商品总重量分别为 $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$, 这是最小值。

注意,可能存在重量相同的多件商品,且每件商品必须放入某个幸运袋中。

数据范围

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