eolymp
bolt
Try our new interface for solving problems

Economy

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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.

Giriş verilənləri

The first line consists the number of test cases t (t100). Each test consists of two lines. First line contains two integers n and k (1n, k100). Second line contains n positive integers c_1, c_2, ..., c_N respectively (1c_i10^6).

Çıxış verilənləri

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.

Nümunə

Giriş verilənləri #1
1
3 3
2 5 6
Çıxış verilənləri #1
13
Mənbə ACM ICPC 2012-2013, NEERC, Krasnojarsk