Minimize Maximum Subarray Sum

You are given an array of positive integers and a positive integer k. Your task is to divide the array into k contiguous subarrays such that the maximum sum among these subarrays is minimized.

More formally, suppose the array is \(a_1, a_2, \dots, a_n\). You need to partition this array into k non-empty contiguous segments. Define \(S_i\) as the sum of the numbers in the i-th subarray. Your goal is to minimize \(\max\{S_1, S_2, \dots, S_k\}\).

Input and Output via standard IO: The solution should read from stdin and print the output to stdout.

inputFormat

The first line contains two integers n and k, where n is the number of elements in the array and k is the number of subarrays to split into. The second line contains n space-separated positive integers representing the array elements.

Example:

5 2
7 2 5 10 8

outputFormat

Output a single integer which is the minimized maximum subarray sum after splitting the array into k contiguous parts.

Example:

18

## sample

5 2
7 2 5 10 8

18