Split the array with a minimum sum
Given
n integers 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