Minimize Largest Subarray Sum Partition

Given an array of positive integers \(A = [a_1, a_2, \ldots, a_n]\) and an integer \(k\), partition the array into \(k\) contiguous non-empty subarrays such that the largest sum among these subarrays is minimized. In other words, you need to split the array into exactly \(k\) parts where the cost of a partition is defined as the maximum sum of its parts, and you want to minimize that cost.

Example:

Input:  A = [7, 2, 5, 10, 8], k = 2
Output: 18
Explanation: There are several ways to split the array into 2 subarrays. The optimal way is to split it as [7,2,5] and [10,8], where the sums are 14 and 18 respectively. The largest sum is 18, which is the minimum possible among all valid splits.

</p>

The problem can be formulated mathematically as finding the minimum value \(X\) such that the array can be partitioned into \(k\) or fewer parts with each part having a sum \(\le X\). Use algorithms involving binary search to efficiently obtain the answer.

inputFormat

The input is read from standard input (stdin). It begins with an integer \(T\) denoting the number of test cases. For each test case, 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 positive integers representing the array \(A\).

T
n k
a1 a2 ... an
(repeat for T test cases)

outputFormat

For each test case, output a single line to standard output (stdout) containing the minimized largest subarray sum.

result_1
result_2
...
result_T

## sample

2
5 2
7 2 5 10 8
5 3
1 2 3 4 5

18
6

</p>