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 AA of NN integers. The game lasts for KK rounds.

Each round goes like this:

  1. Alice picks an integerXX where 0XCurrent length of the Array.0 \leq X \leq Current\ length\ of\ the\ Array.

  2. Bob either erases the first XX elements from the array or keeps only these XX 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 TT denoting the number of test cases. The description of TT test cases follows:

Each testcase will start with a line containing two positive integers NN, KK denoting the number of elements of the array and the number of rounds the game is played respectively. Next line will contain NN space separated integers A1,A2,,ANA_1, A_2, \dots, A_N.

Constraints

1T10001 \leq T \leq 1000
1Ai1091 \leq A_i \leq 10^9

Subtask 1 (16 points)

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

Subtask 2 (32 points)

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

Subtask 3 (52 points)

1N,K1051 \leq N, K \leq 10^5
Sum of NN over all testcases does not exceed 10610^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=3X = 3.
Bob erases the first XX elements and the remaining elements are: [4,5][4, 5].

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

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

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

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

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

    Discussion

    Statistics


    59% Solution Ratio

    user.964301Earliest, 4M ago

    Deshi_TouristFastest, 0.1s

    Deshi_TouristLightest, 393 kB

    sakib.17442Shortest, 744B

    Submit

    Login to submit

    Editorial

    Subtask 1 Alice can force the final array to have only one element if the number of rounds, KKK is a...

    Toph uses cookies. By continuing you agree to our Cookie Policy.