Economy#3927
You and your k-1 friends want to buy books from a shop. Book number has price c_i. However, the seller does not like when a single customer buys too many books, so he increases the price for customers who buy multiple books. Specifically, if a customer has already bought books, then to buy book number he must pay (x+1) \cdot c_i dollars.
You and your k-1 friends want to buy all books, distributing purchases among yourselves so that the total amount spent is minimized.
The first line contains the number of test cases (t \leq 100). Each test case consists of two lines. The first line contains integers and (1 \leq n, k \leq 100). The second line contains positive integers c_1, c_2, \ldots, c_n (1 \leq c_i \leq 10^6) — the prices of the books.
For each test case, print on a separate line the minimum total amount of money needed to buy all books.
Example 1