GOLDCOIN - Gold distribution

no tags 

 

Ankul and Rohil have been awarded with N gold coins in a recent programming competition. Now they want
to divide these N coins. But there is a problem, weight of each coin is not equal.Both of them know that
dividing these coins optimally is an NP-Complete problem. So they have decided to put all the coins on a stack and
divide them in the following manner:
They both take their turn alternatively and in each turn atmost K coins from the top of stack can be taken.
Ankul always start first. Consider that both of them are infinitely intelligent so they will always take the
best possible move. you have to find the maximum weight which Ankul and Rohil will be able to get.

Ankul and Rohil have been awarded with N gold coins in a recent programming competition. Now they want to divide these N coins. But there is a problem, weight of each coin is not equal. Both of them know that dividing these coins optimally is an NP-Complete problem. So they have decided to put all the coins on a stack and divide them in the following manner: 

They both take their turn alternatively and in each turn at most K coins from the top of stack can be taken. Ankul always start first. Consider that both of them are infinitely intelligent so they will always take the best possible move. you have to find the maximum weight which Ankul and Rohil will be able to get.

Input

First line of input contains T (1<=T<=30) the number of test cases then T test cases follow. First line of each test cases contains two space separated integers N and K (1<=N<=10000 and 1<=K<=10). 2nd line contains N space separated integers (w1, w2,...wn), wi if the weight of ith gold coins from the top.(0<=wi<=1000)

Output

For each test case print one line which contains 2 space separated integers A and R. A and R are the maximum weight of gold which Ankul and Rohil will be able to take respectively.

Example

Input:
2
3 2
1 2 3
10 4
2 1 0 1 3 9 2 0 1 5

Output:
3 3
14 10


Added by:Mahesh Chandra Sharma
Date:2011-01-20
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem