Farmer John は驚くべき会計の達人で、農場の運営資金が尽きそうだと気づきました。今後 $N$ 日（$1 \le N \le 100,000$）の毎日に必要な正確な金額（$1 \le money_{i} \le 10,000$）を計算し記録しました。

FJ は「fajomonths」と呼ぶ、順に並んだちょうど $M$ 個（$1 \le M \le N$）の会計期間の予算を作ります。各期間は連続する一日以上で、各日はちょうど一つの期間に属します。

支出が最大の期間の支出を最小化するよう期間を区切り、月間支出限度を決めます。

入力

行 1：空白区切りの 2 整数 $N$ と $M$。行 $2\ldots N+1$：行 $i+1$ は Farmer John が $i$ 日目に使うドル額。

出力

行 1：Farmer John が採用できる最小の月間限度。

入出力例

入力 1

7 5
100
400
300
100
500
101
400

出力 1

500

注記

初めの二日を一月、三日目と四日目を一月、最後の三日をそれぞれ一月にすれば、どの月も最大 500 ドルです。他の区切り方では必要な最小月間限度がもっと大きくなります。

問題出典：USACO 2007 年 3 月。