Given an integer sequence containing n elements (numbered from 1 to n), your task is to find the minimum value M so that we can find k + 1 integers 0 = p(0) < p(1) < p(2) < ... < p(k-1) < p(k) = n, such that for any i from 0 to k - 1, the sum of elements from postition p(i)+1 to postition p(i+1) is not greater than M.

Input

The first line of input contains the number of test cases nTest (1 <= nTest <= 10).

Each test case contains:

The first line contains n, k. (1 <= k <= n <= 15000)

Each of the next n lines contains an integer of the sequence with value range from -30000 to 30000.

Output

For each test case write the minimum number M in a separate line.

Example

Input:
1
9 4
1
1
1
3
2
2
1
3
1

Output:
5