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.