Minimize Maximum Subarray Sum

You are given an array of n integers, and you need to partition this array into k non-empty contiguous subarrays. The objective is to minimize the maximum sum among these subarrays.

Let \( M \) denote the maximum subarray sum after partitioning. Note that \( M \) must satisfy the inequality:

[ \max(nums) \le M \le \sum_{i=1}^{n} nums[i] ]

Your task is to compute the minimum possible value of \( M \) such that the array can be split into at most k parts with each part having a sum not exceeding \( M \). A binary search approach combined with a greedy check is recommended to solve this problem efficiently.

inputFormat

The first line of input contains an integer T, the number of test cases. For each test case:

• The first line contains two integers: n (the number of elements in the array) and k (the number of subarrays).
• The second line contains n space-separated integers representing the array elements.

outputFormat

For each test case, output a single integer representing the minimized maximum subarray sum. Each result should be printed on a new line.

## sample

3
5 2
1 2 3 4 5
3 1
1 2 3
3 3
1 2 3

9
6
3

</p>