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.
First line contains two numbers n and k (n≤106,1≤k≤n). Second line contains n positive integers, each no more than 109.
Print the minimum possible sub-array sum.
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.