10691069 SUSTech Online Judge
Problem 1069 --Combination

1069: Combination

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 556  Solved: 166
[Submit][Status][Web Board]


There are n values, you are asked to combine them to one, you are allowed to combine at most k values to one each time, and the cost of one combination is the sum of all values that you combine, print the minimum cost.


The first line will be an integer T, which is the number of test cases. (1 <= T <= 10). For each test case, the first line will be two integer n(1 <= n <= 105) and k(2 <= k <= 105), n is the number of values, k has been explained in problem description. The second line are those n values, we promise that (n - 1) % (k - 1) = 0.


For each test output the minimum cost.

Sample Input

3 2
1 2 3

Sample Output