Minimize Maximum Subarray Sum Partition

You are given an array \(A\) of \(N\) positive integers and an integer \(K\). The task is to split the array into \(K\) contiguous subarrays such that the maximum sum among these subarrays is minimized. This problem can be solved using a binary search approach combined with a greedy validation technique.

Let \(S\) be a candidate maximum subarray sum. We check whether we can partition the array \(A\) into at most \(K\) subarrays such that the sum of each subarray does not exceed \(S\). The search range for \(S\) is \(\max(A) \le S \le \sum_{i=1}^{N} A_i\). Using binary search we find the minimum \(S\) for which the partitioning is possible.

Input Constraints:

• \(1 \leq T \leq 10\) — number of test cases
• For each test case:
• \(1 \leq N \leq 10^5\)
• \(1 \leq K \leq N\)
• \(1 \leq A_i \leq 10^9\)

The final answer for each test case is the minimal maximum subarray sum that can be achieved by an appropriate partition.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case consists of two lines:

1. The first line contains two integers \(N\) and \(K\) separated by a space.
2. The second line contains \(N\) space-separated integers, representing the array \(A\).

outputFormat

For each test case, output a single integer: the minimized value of the maximum subarray sum after partitioning the array into \(K\) subarrays. Each answer should be printed on a new line.

## sample

2
7 3
10 5 2 7 1 5 6
5 2
1 2 3 4 5

14
9

</p>