D: 水槽

問題

AORイカちゃんは縦 $1$ 横 $N$ の大きさの水槽をもらった。水槽は水を入れるのに十分な高さがある。 水槽には $N-1$ 個の仕切りがあり $N$ 個の区画に等間隔に区切られている。 ここに水を注いだところ、各区画の水の高さは $a_i$ になった。

AORイカちゃんはいくつか仕切りを取り除き、区画の数を $M$ 個以下にすることにした。 仕切りを取り除き終わった時、各区画の水の高さの総和の最大値を求めよ。

なお、仕切りの厚さは無視できるものとする。

制約

• $1 \le N \le 500$
• $1 \le M \le N$
• $1 \le a_i \le 10^9$
• 入力は全て整数

入力

$N \ M$
$a_1 \cdots a_N$

出力

各区画の水の高さの総和の最大値を一行で出力せよ。また末尾に改行を出力せよ。 相対誤差または絶対誤差が $10^{-6}$ 以下であれば許容される。

サンプル

サンプル入力 1

5 3
9 1 2 3 9

サンプル出力 1

20.000000

$a_2$ と $a_3$ 、$a_3$ と $a_4$ の間の仕切りをとると、その区画の水の高さは $\frac{(1 + 2 + 3)}{3} = 2$ となる。 各区画の水の高さは $9 \ 2 \ 9$ となりこれが最大である。

サンプル入力 2

4 1
14 4 9 7

サンプル出力 2

8.500000

サンプル入力 3

8 3
11 18 9 20 4 18 12 14

サンプル出力 3

44.666667