Economy
You are the captain of a team that has just won World Final ACM ICPC and you have to celebrate your victory now. You gather k-1 friends and go to the nearest store to buy n bottles of [here may be your advertisement!]. Bottle number i has price c_i. Unfortunately the seller does not like his customers to buy too many bottles, so he changes the price of bottle for a customer who had already bought them before. More precisely, if a customer has already bought x bottles, he has to pay (x+1)·c_i dollars to buy bottle number i.
You and your k-1 friends want to buy all n bottles in such a way that you spend the as little money as possible.
Input
The first line consists the number of test cases t (t ≤ 100). Each test consists of two lines. First line contains two integers n and k (1 ≤ n, k ≤ 100). Second line contains n positive integers c_1, c_2, ..., c_N respectively (1 ≤ c_i ≤ 10^6).
Output
For each test case print in a separate line the minimum amount of money you (and your friends) have to pay in order to buy all the n bottles.