Splitting Sum

Problem Description

You are given a positive integer sequence $A_{1\dots N}$ of length $N$. Split it into $M$ ($M \le N$) contiguous segments so that each segment is consecutive, and the maximum of the segment sums is minimized.

What "maximum minimized" means:

For example, to split the sequence $4, 2, 4, 5, 1$ into $3$ segments:

• Split as $[4, 2][4, 5][1]$: the segment sums are $6$, $9$, $1$; the maximum is $9$.
• Split as $[4][2, 4][5, 1]$: the segment sums are $4$, $6$, $6$; the maximum is $6$.

No matter how you split it, the maximum cannot be smaller than $6$.

So for the sequence $4, 2, 4, 5, 1$ split into $3$ segments, the minimum possible value of the maximum segment sum is $6$.

Input Format

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

The second line contains $N$ space-separated non-negative integers $A_i$, as described above.

Output Format

Output one positive integer: the minimized maximum segment sum.

Sample Input

5 3
4 2 4 5 1

Sample Output

6

Constraints

$1 \le N \le 10^5,\ M \le N,\ A_i \le 10^8$.