# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Fair Share

By Aashiq · Limits 1s, 512 MB

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

InputOutput
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$.

### Statistics

56% Solution Ratio

user.964301Earliest, 1M ago

Deshi_TouristFastest, 0.1s

Deshi_TouristLightest, 393 kB

sakib.17442Shortest, 744B