Optimal Relay Race Division

You are given a relay race problem. In this race, a sequence of N segments with associated times is provided. The race must be divided among K runners so that each runner runs a contiguous block of segments. The objective is to minimize the maximum time any single runner spends.

Formally, given an array of segment times \(a_1, a_2, \dots, a_N\), partition the array into \(K\) contiguous groups such that the maximum sum of any group is as small as possible. You need to output this minimal possible value.

Hint: Use binary search over possible maximum times and a greedy strategy to verify if a given maximum time is feasible.

inputFormat

The input is given via stdin and has the following structure:

• The first line contains a single integer T, representing the number of test cases.
• For each test case:
• The first line contains two integers N and K -- the number of segments and the number of runners, respectively.
• The second line contains N space-separated integers representing the time required for each segment.

outputFormat

For each test case, output a single integer representing the minimal maximum segment time a runner would need to run if the segments are optimally partitioned. The answers should be printed to stdout, one per line.

## sample

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

9
4

</p>