Minimize Maximum Subarray Sum

You are given an array of n positive integers and an integer K. Your task is to split the array into K contiguous subarrays such that the maximum sum among these subarrays is minimized. Determine the minimized maximum subarray sum.

Formally, if the array is divided into K contiguous parts, let S_i be the sum of the i-th subarray. You need to find the smallest possible X such that it is possible to partition the array into K subarrays and for all parts, S_i \le X holds.

The solution involves performing a binary search on the answer and validating each mid value by simulating the splitting of the array.

inputFormat

The first line of input contains two integers, n and K, where n is the number of elements in the array and K is the number of subarrays you need to form. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer denoting the minimized maximum subarray sum that can be achieved by splitting the array into K contiguous subarrays.

## sample

5 2
1 2 3 4 5

9

</p>