Minimized Maximum Subarray Sum Partition

You are given an array of positive integers \(a_1, a_2, \dots, a_m\) and an integer \(n\). Your task is to partition the array into exactly \(n\) contiguous subarrays such that the maximum sum among these subarrays is minimized. In other words, if the sums of the subarrays are \(S_1, S_2, \dots, S_n\), you need to find the minimum possible value of \(\max(S_1, S_2, \dots, S_n)\).

Example 1: For the array [7, 2, 5, 10, 8] and \(n = 2\), one optimal partition is [7, 2, 5] and [10, 8] with sums 14 and 18 respectively, so the answer is 18.

Example 2: For the array [1, 2, 3, 4, 5] and \(n = 2\), one optimal partition is [1, 2, 3] and [4, 5] with sums 6 and 9 respectively, so the answer is 9.

Note: It is guaranteed that the array contains only positive integers.

inputFormat

The input is given from stdin in the following format:

• The first line contains two space-separated integers \(m\) and \(n\), where \(m\) is the number of elements in the array and \(n\) is the number of partitions.
• The second line contains \(m\) space-separated positive integers representing the array elements.

outputFormat

Output to stdout a single integer which is the minimized maximum subarray sum achievable by partitioning the array into \(n\) contiguous subarrays.

## sample

5 2
7 2 5 10 8

18

</p>