Farmer John 是驚人的會計高手，意識到經營農場的錢可能會耗盡。他已計算並記錄未來 $N$（$1 \le N \le 100,000$）天每天所需的準確支出（$1 \le money_{i} \le 10,000$）。

FJ 要為按順序排列的恰好 $M$（$1 \le M \le N$）個財務期間制定預算，稱它們為「fajomonths」。每個期間包含一個或多個連續的日子，每天恰好屬於一個期間。

FJ 希望安排這些期間，使支出最高的期間的支出盡可能小，從而確定月度支出上限。

輸入格式

第 1 行：兩個空格分隔的整數 $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

說明

若 Farmer John 將前兩天組成一個月，第 3、4 天組成一個月，最後三天各自組成一個月，每月支出至多 500 美元。其他任何安排都需要更大的最小月度上限。

題目來源：USACO 2007 年 3 月。