Minimum Maximum Subarray Sum Partition Problem

You are given an array \(A\) consisting of \(N\) integers. Your task is to partition the array into \(K\) non-empty contiguous subarrays such that the maximum sum among these subarrays is minimized.

Formally, suppose you partition \(A\) into segments \(S_1, S_2, \dots, S_K\) where each \(S_i\) is a contiguous segment and \(\bigcup_{i=1}^{K} S_i = A\). Let \(sum(S_i)\) be the sum of elements in segment \(S_i\). You need to minimize \(\max_{1 \leq i \leq K} sum(S_i)\). It is guaranteed that a valid partition always exists.

Note: The optimal solution can be found using a binary search strategy coupled with a greedy feasibility check.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case consists of two lines. The first line contains two integers \(N\) and \(K\) -- the number of elements in the array and the number of subarrays respectively. The second line contains \(N\) space-separated integers representing the array \(A\).

outputFormat

For each test case, output a single line with one integer: the minimum possible value of the maximum subarray sum after partitioning the array into \(K\) contiguous subarrays.

## sample

1
7 3
5 3 1 2 6 8 2

10

</p>