Description

Given a sequence of positive integers $A_{1\sim N}$ of length $N$, you need to partition it into $M$ ($M \leq N$) contiguous segments, such that the maximum segment sum is minimized.

About minimizing the maximum:

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

Partition it as:

The sum of the first segment is $6$, the sum of the second segment is $9$, the sum of the third segment is $1$, and the maximum of these sums is $9$.

Partition it as:

The sum of the first segment is $4$, the sum of the second segment is $6$, the sum of the third segment is $6$, and the maximum of these sums is $6$.

Moreover, no matter how you partition it, the maximum will not be smaller than $6$.

Therefore, for the sequence $4\ 2\ 4\ 5\ 1$ divided into $3$ segments, the minimum possible maximum segment sum is $6$.

Input Format

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

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

Output Format

A single positive integer: the minimum possible value of the maximum segment sum.

5 3
4 2 4 5 1

6

Hint

Constraints:

• For $20\%$ of the testdata, $N \leq 10$.
• For $40\%$ of the testdata, $N \leq 1000$.
• For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $M \leq N$, $A_i < 10^8$, and the answer does not exceed $10^9$.

Translated by ChatGPT 5