We are given an array V with N positive integers. We want to split it into M subarrays (contiguous), each of them of even length. The cost of one subarray equals the maximum between the sum of of the elements in first half of the subarray, on the one hand, and the sum of the elements in the second half of the array, on the other hand. The total cost of a split is the maximum of the costs if the subarrays defining that split.

Compute the minimum total cost of a split of the array V.

Input:

The file split2.in contains on the first line T, the number of tests. Each test contains 2 lines: on the first one we have N and M, on the second one the array V.

Output:

Write in the output file split2.out (each on a line) the requested value for each of the T tests, respectively.

Constraints:

1 <= T <= 50

1 <= M <= N <= 1000

1 <= V[i] <= 10000

N is even.

For each test there will be a correct split.

Example:

split2.in

1

10 3

1 2 4 2 4 5 2 2 1 3

split2.out

6

==

The split will be:

1 2 4 2 | 4 5 | 2 2 1 3

First subarray 1 2 4 2 has cost 6.

Second subarray 4 5 has cost 5.

Third subarray 2 2 1 3 has cost 4.

Please help me write a java or c++ code for this problem