問題文

ある日、Rhoたち $K$ 人の魔法少女は、アルティメットThistleから $N$ 個のビーズが連なった円環を受け取りました。
$N$ 個のビーズそれぞれには、$1,2,\dots,N$ と番号が振られています。
$i(2 \leq i \leq N-1)$ 番目のビーズはビーズ $i-1$ と $i+1$ に隣り合っていて、$1$ 番目のビーズはビーズ $N$ と $2$、$N$ 番目のビーズはビーズ $N-1$ と $1$ に隣り合っています。

これらのビーズにはアルティメットThistleが魔力を込めていて、魔力の質によって1つ1つに価値が存在します。
具体的には、$i$ 番目のビーズの価値は $A_i$ です。

彼女たちはこの円環を連続するビーズから成る $K$ 個の区間に分割し、これを $K$ 人で分けあうことにしました。
ただ、分け方が平等でないと抗争に発展してしまうので、それぞれの分け前のビーズの価値の総和の最小値を $M$ としたとき、$M$ が最大になるように分割することにしました。

さて、彼女たちのマスコットであるあなたは、彼女たちを陰から導くため、上のような分割をしたときの $M$ を求めることにしました。

入力

$N\ K$
$A_1\ A_2\ \dots\ A_N$

入力は全て整数である
$1\leq K\leq N\leq 10^5$
$1\leq A_i\leq 10^9 (1\leq i\leq N)$

出力

$M$ の最大値を出力してください。 最後に改行してください。

サンプル

6 4
8 6 9 1 2 1

4

15 7
12 9 11 15 15 11 9 7 2 3 1 14 15 6 11

15