AT_abc332_e [ABC332E] Lucky bag

[problemUrl]: https://atcoder.jp/contests/abc332/tasks/abc332_e AtCoder 社は、[オンラインショップ](https://suzuri.jp/AtCoder/home)でグッズを販売しています。 今、$ N $ 個のグッズが社内に残っています。 ここで、$ i $ $ (1\leq\ i\leq\ 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 $ 袋のうちちょうど $ 1 $ つの福袋に入っている** ようにするものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D $ $ W_1 $ $ W_2 $ $ \ldots $ $ W_N $

各福袋に入ったグッズの重さの合計の分散が最小になるようにグッズを分けた時の分散の値を出力せよ。 出力は、真の値との絶対誤差または相対誤差が $ 10^{-6} $ 以下のとき正解と判定される。

### 制約 - $ 2\ \leq\ D\leq\ N\leq\ 15 $ - $ 1\ \leq\ W_i\leq\ 10^8 $ - 入力はすべて整数 ### Sample Explanation 1 $ 1 $ つめの福袋に $ 1,3 $ 個目のグッズを、 $ 2 $ つめの福袋に $ 2,5 $ 個目のグッズを、 $ 3 $ つめの福袋に $ 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 $ となり、このときが最小です。 同じ重さのグッズが複数存在し得ること、 各グッズはいずれかの福袋に入っている必要があることに注意してください。