Minimize Maximum Subarray Sum

You are given an array of n positive integers and an integer k. You are required to partition the array into at most k contiguous subarrays such that the maximum sum of these subarrays is minimized.

Formally, let the array be \(a_1, a_2, \ldots, a_n\). Partition the array into \(m\) contiguous parts (where \(1 \le m \le k\)). For a valid partition, let \(s_i\) be the sum of the elements in the i-th subarray. Your task is to choose a partition so that \(\max(s_1, s_2, \ldots, s_m)\) is as small as possible, and output this minimum possible value.

Note: It is guaranteed that the array elements are positive, so at least one valid partition exists.

inputFormat

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

• The first line contains two integers n and k (with \(1 \le n \le 10^5\)), where n is the number of elements in the array and k is the maximum number of subarrays allowed.
• The second line contains n space-separated positive integers representing the elements of the array.

outputFormat

Output to stdout a single integer: the minimum possible value of the maximum subarray sum when partitioning the array into at most k contiguous subarrays.

5 3
7 2 5 10 8

14