Hint: Use binary search on the answer!

Sunny has just became the god of Lyneland. He wants to reassign the lands of Lyneland to us, mere mortals.
The $N$ lands of Lyneland is in the form of a line. Each land has a number $q_i$, representing the quality of the land. Sunny wants to assign a connected segment of lands to each $M$ of the mere mortals. Each land must be assigned. To be as fair as possible, Sunny does not want any mere mortals to have lands such that the total sum of quality exceeds $Q$. Can you help Sunny to find the minimum such $Q$?

Input

The first line consists of two integers, $N$ and $M$.
The second line consists of $N$ integers, the quality of lands $q_i$.

Output

Output an integer, the minimum possible $Q$.

Constraints

For all testcases: $1 \le M \le N \le 10^6$, $1 \le q_i \le 10^9$
Subtask 1 (10%): $N \le 10$, $q_i \le 10^6$
Subtask 2 (90%): No other constraints