Minimize Maximum Group Sum in Dumpling Distribution

You are given a sequence of plates containing dumplings, where each plate has a deliciousness value. Your task is to partition the sequence into K contiguous groups (preserving the order) such that the maximum sum over all groups is minimized.

Formally, let the sequence be \(A = [a_1, a_2, \ldots, a_N]\). You need to split it into exactly \(K\) contiguous segments \(S_1, S_2, \ldots, S_K\). For each segment \(S_i\), let \(s_i\) be the sum of its elements. Your objective is to minimize $$\max(s_1, s_2, \ldots, s_K)$$ subject to maintaining the original order of the plates.

A typical approach to solve this problem is using binary search along with a greedy algorithm to check whether a given threshold can form at most \(K\) groups.

inputFormat

The input begins with a single integer \(T\) on the first line, representing the number of test cases.

Each test case consists of two lines:

• The first line contains two integers \(N\) and \(K\) where \(N\) is the number of plates and \(K\) is the number of groups into which you must partition the sequence.
• The second line contains \(N\) space-separated integers, representing the deliciousness values of the plates in order.

outputFormat

For each test case, output a single line containing one integer: the minimized maximum sum among the groups after partitioning.

## sample

1
5 2
1 2 3 4 5

9

</p>