Minimize Maximum Segment Sum

Given a sequence of N positive integers \(A_1, A_2, \ldots, A_N\), you are required to split the sequence into exactly M contiguous segments (with \(M \leq N\)). The goal is to minimize the maximum sum among all segments.

For example, consider the sequence:

[ 4 \quad 2 \quad 4 \quad 5 \quad 1 ]

If we split into 3 segments as follows:

[ [4;2]\quad[4;5]\quad[1] ]

the segment sums are 6, 9, and 1, with a maximum of 9.

If we split as:

[ [4]\quad[2;4]\quad[5;1] ]

the segment sums are 4, 6, and 6, with a maximum of 6. It can be shown that no matter how the sequence is partitioned into 3 segments, the minimal possible maximum sum is 6.

Your task is to compute this minimal possible maximum segment sum.

inputFormat

The first line contains two integers, N and M (\(1 \leq M \leq N \leq 10^5\)).

The second line contains N positive integers \(A_1, A_2, \ldots, A_N\) (each \(A_i\) is between 1 and \(10^9\)).

outputFormat

Output a single integer, which is the minimal possible maximum segment sum when the sequence is divided into M contiguous segments.

sample

5 3
4 2 4 5 1

6