Description

Given a sequence of positive integers $A$ of length $N$, it is to be divided into $M$ segments. Each segment must be continuous, and the maximum sum among all segments should be minimized.

For example, consider the sequence $4 \ \ 2 \ \ 4 \ \ 5 \ \ 1$ to be divided into $3$ segments:

If divided as $[4$ $2][4$ $5][1]$, the sums of the segments are $6, 9, 1$, and the maximum sum is $9$;

If divided as $[4][2$ $4][5$ $1]$, the sums of the segments are $4, 6, 6$, and the maximum sum is $6$;

Moreover, no matter how the sequence is divided, the maximum sum cannot be less than $6$.

Thus, the minimum possible maximum sum when dividing the sequence $4 \ \ 2 \ \ 4 \ \ 5 \ \ 1$ into $3$ segments is $6$.

Input Format

The first line contains two positive integers $N$ and $M$;

The second line contains $N$ non-negative integers $A_i$ separated by spaces, as described in the problem.

Output Format

Output a single positive integer, which is the minimum possible maximum sum among all segments.

Sample 1

5 3
4 2 4 5 1

6

Data Range and Hints

For $20\%$ of the data, $N \leq 10$;

For $40\%$ of the data, $N \leq 1000$;

For $100\%$ of the data, $N \leq 10^5$, $M \leq N$, and the sum of $A_i$ does not exceed $10^9$.