Given an array of N elements. You have to divide it into K consecutive segments according to following rule-

(a) Suppose array is A[0 . . N] and you have to divide it into K consecutive segments.

(b) All the segments are valid if and only if their intersection is NULL and their union is given array.

© You need to create segments such that maximum of sum of numbers in each segment is minimum.

See the first sample test case for better explanation.

Input

First line of input contains an integer T denoting number of test cases. Each test case is composed of 2 lines. First line contains two integers N and K. Next line contains N space separated integers which are the elements of given array.

Output

For each test case just print one integer, that is the answer to given test case. Answer each test case in a new line.

Constraints-

1<=T<=30

2<=N<=20

2<=K<=N

1<=A[i]<=1000

Time limit-

1 second

Sample Input

1

9 3

10 20 30 40 50 60 70 80 90

Sample Output

170

Explanation

You can divide the given array A[] into these 3 segments-

(i) A[0] to A[4] : sum= 150

(ii) A[5] to A[6] : sum= 130

(iii) A[7] to A[8]: sum= 170

Maximum of these sums is 170. There is no other way to choose 3 segments so as to minimize this maximum.