Partition Scores

You are given a list of positive integers representing scores and an integer k. Your task is to partition the list into k contiguous groups (maintaining the original order) such that the maximum sum among these groups is minimized. In other words, you need to split the array into k continuous segments so that the largest segment sum is as small as possible.

For example, if the scores are [10, 20, 30, 40, 50] and k = 3, one optimal partition is [10, 20, 30], [40], [50] with the maximum group sum being 60. The answer in this case is 60.

Note: Your solution should read input from standard input (stdin) and write the output to standard output (stdout). All formulas, where applicable, must be represented in LaTeX format. For example, the binary search condition can be represented as \(\text{if } S \leq M\text{ then...}\) (though not mandatory here).

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 space-separated integers, (n) and (k), where (n) is the number of scores and (k) is the number of groups.
2. The second line contains (n) space-separated positive integers representing the scores.

Example:

1 5 3 10 20 30 40 50

outputFormat

For each test case, output a single integer on a new line representing the minimized maximum group sum after partitioning the scores.## sample

1
5 3
10 20 30 40 50

60