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

Explanation

1. [1 2 3] [6 2] ⇒ maximum subarray sum is 6 + 2 = 8

2. [1 2] [10] [3 2] ⇒ maximum subarray sum is 10