Split the array with a minimum sum
Given
n
integers
and an integer k
, you are asked to split the array into k
contiguous parts so that the maximum subarray sum is as small as possible. Input
The first line of the input contains two integers
n
(1 ≤ n ≤ ) and k
(1 ≤ k ≤ n).The next line contains space-separated integers
( ≤ ≤ ). Output
The program should print the maximum subarray sum that is as small as possible.
Examples
Input | Output |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
Explanation
[1 2 3] [6 2]
⇒ maximum subarray sum is 6 + 2 = 8
[1 2] [10] [3 2]
⇒ maximum subarray sum is 10
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB