Given array of n elements and number k. Split the given array into k sub-arrays (they must cover all the elements). The maximum sub-array sum achievable out of k sub-arrays formed, must be minimum possible. Find that possible sub-array sum.

Input

First line contains two numbers n and k (n ≤ 106, 1 ≤ k ≤ n). Second line contains n positive integers, each no more than 109.

Output

Print the minimum possible sub-array sum.

Explanation

For the first sample the optimal split is {1, 2}, {3}, {4}. Maximum sum of all sub-arrays is 4, which is minimum possible for 3 subarrays.

For the second sample the optimal split is {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 1}. Maximum sum of all sub-arrays is 10, which is minimum possible for 3 subarrays.