Balanced Banquet Table Grouping

A banquet hall has N tables arranged in a row, and each table has a certain number of plates. Each plate contains a special dish. The task is to partition the tables into M contiguous groups (\(1 \leq M \leq N\)) such that the sum of the dishes in each group is as balanced as possible. In other words, you need to minimize the maximum sum of dishes over all groups.

More formally, given a sequence of dish counts \(a_1, a_2, \dots, a_N\), you must split this sequence into M contiguous segments. Let \(S_i\) denote the sum of dishes in the i^th group. Your goal is to minimize the value of \(\max_{1 \leq i \leq M} S_i\). The answer is the minimum possible value of this maximum sum.

Example:

Input:
2
5 3
10 20 30 40 50
4 2
5 10 5 5
Output:
60
15

</p>

inputFormat

The first line of input contains a single integer T indicating the number of test cases. Each test case follows and is described as:

• The first line contains two space-separated integers N and M, where N is the number of tables and M is the number of groups.
• The next line contains N space-separated integers, representing the number of dishes on each table.

You should read input from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line, representing the minimum possible value of the maximum sum of dishes in any group, when the tables are divided optimally. Write your output to standard output (stdout).

## sample

2
5 3
10 20 30 40 50
4 2
5 10 5 5

60
15

</p>