Migrated from Lutece 144 Divide

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$N$ numbers are given in a line, we want you to divide them into no more than $M$ piles so that the maximum number of the sum of each pile is minimal. You can't change the number's order.

Input

The first line contains a number $T$, denote the number of test cases.

For each test case,

In the first line, you will get $2$ numbers $N$ and $M$ ($1\leq M\leq N\leq 1000$) as described above.

In the next line, you will get the $N$ integers, all the integers are in the range of $[-100,100]$.

Output

For each test case, you should output a number in a line denote the minimal maximum sum.

Samples

2
9 3
1 9 2 4 7 3 0 6 5
3 2
1 3 -2

14
1

Note

In the first case, you can divide the numbers as 1 9 2 / 4 7 3 0 / 6 5

In the second case, you can divide the numbers as 1 / 3 -2

Resources

Sichuan State Programming Contest 2008