Minimizing Maximum Subarray Sum

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

In other words, if you divide the array into k contiguous parts, let S_i be the sum of the i-th part, you need to minimize max(S₁, S₂, \dots, S_k). This is a typical optimization problem that can be solved using binary search combined with a greedy strategy.

It is guaranteed that a valid partition always exists, and you are required to print the minimized maximum subarray sum.

inputFormat

The input is read from stdin and consists of two lines:

• 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 partition into.
• The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer to stdout which is the minimized maximum subarray sum after partitioning the array into k contiguous subarrays.

5 2
7 2 5 10 8

18