Given array of elements and number . Split the given array into sub-arrays (they must cover all the elements). The maximum sub-array sum achievable out of sub-arrays formed, must be minimum possible. Find that possible sub-array sum.
First line contains two numbers and . Second line contains positive integers, each no more than .
Print the minimum possible sub-array sum.
For the first sample the optimal split is . Maximum sum of all sub-arrays is , which is minimum possible for subarrays.
For the second sample the optimal split is . Maximum sum of all sub-arrays is , which is minimum possible for subarrays.