750. Chocolate Promotion

0

Easy

Martin's friend owns a bakery that offers N different varieties of chocolates. However, there is a special promotion where if Martin buys one chocolate, he can get up to K additional chocolates for free, each of a different variety. The goal is to determine the minimum amount of money Martin needs to spend in order to buy all the different varieties of chocolates, taking advantage of this offer.

Input Format

The input consists of T test cases. Each test case begins with a line containing two integers, N and K, representing the number of chocolate varieties and the maximum number of free chocolates Martin can get, respectively. The next line contains N integers, representing the prices of each chocolate variety.

Output Format

For each test case, output a single integer on a new line, representing the minimum amount of money required to buy all the chocolate varieties.

Example

Input

1
4 2
3 2 1 4

Output

3

Constraints

1 <= T <= 50
1 <= N <= 1000
0 <= K <= N-1
1 <= A

_{i}<= 100Loading...

View Submissions

Console