Fair Share

Alice and Bob are playing a game on an array $A$ of $N$ integers. The game lasts for $K$ rounds.

Each round goes like this:

1. Alice picks an integer$X$ where $0 \leq X \leq Current\ length\ of\ the\ Array.$

2. Bob either erases the first $X$ elements from the array or keeps only these $X$ elements in the array erasing the rest of them.

Now, Alice tries to minimize the sum of the elements of the final array and Bob tries to maximize it. If they both play optimally, what will be the sum of the elements of the final array?

Note that, the array may even become empty during the game and the sum of elements of an empty array is 0.

Input

The first line of the input will contain a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows:

Each testcase will start with a line containing two positive integers $N$, $K$ denoting the number of elements of the array and the number of rounds the game is played respectively. Next line will contain $N$ space separated integers $A_1, A_2, \dots, A_N$.

Constraints

$1 \leq T \leq 1000$
$1 \leq A_i \leq 10^9$

Subtask 1 (16 points)

$1 \leq N \leq 10^5$
$K = 64$
Sum of $N$ over all testcases does not exceed $10^6$

Subtask 2 (32 points)

$1 \leq N, K \leq 10^3$
Sum of $N$ over all testcases does not exceed $10^4$

Subtask 3 (52 points)

$1 \leq N, K \leq 10^5$
Sum of $N$ over all testcases does not exceed $10^6$

Output

For each testcase, output in a line, the sum of the elements of the array after the game ends. See sample for details.

Sample

Input	Output
3 5 1 1 2 3 4 5 5 2 1 2 3 4 5 5 3 1 2 3 4 5	9 5 5

In the first testcase,
1st round:
Alice picks $X = 3$.
Bob erases the first $X$ elements and the remaining elements are: $[4, 5]$.

The sum of the elements of the array after the game ends $= 4 + 5 = 9$.

In the third testcase,
1st round:
Alice picks $X = 1$.
Bob erases the first $X$ elements and the remaining elements are: $[2,3,4,5]$.

2nd round:
Alice picks $X = 3$.
Bob keeps the first $X$ elements and erases the rest of them.
The remaining elements are: $[2,3,4]$.

3rd round:
Alice picks $X = 2$.
Bob keeps the first $X$ elements and erases the rest of them.
The remaining elements are: $[2,3]$.

The sum of the elements of the array after the game ends $= 2+3=5$.