The setter of this problem was very busy arranging Intra KUET Programming Contest. So he decided to write a simple statement for this problem.
You are given an array A having N ( 1 ≤ N ≤ 105 ) integers. You can perform some operation on this array. An operation means you can take on element of the array, and you can remove the element of the array. There is a cost for performing this operation. This cost is given to you. But this cost is not constant.
Let's the initially the cost is K.
For the first element you want to delete, the cost is K.
For the second element you want to delete, the cost is K-1.
For the third element you want to delete, the cost is K-2.
And so on until the cost K becomes 0. After that, the K does not decrease anymore.
Generally, when you erase an element from the array, the cost is K and after that, the cost decreases by 1 if it is not already 0.
And you cannot remove an element from empty array.
Your score is the sum of all the values of the array A minus the total cost you incurred. Can you tell the maximum score you can obtain?
The first line contains T denoting the number of test cases.
For each test case the details is given below:
The first line for each test case starts with N and K. The number of elements of the array and the initial cost for removing an element.
Next line contains N integers, each of the number having range -109 ≤ ai ≤ 109
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 105
1 ≤ K ≤ 109
-109 ≤ ai ≤ 109
Print T lines for each test case. Each of the line should contain the maximum score you can obtain.
| Input | Output |
|---|---|
2 5 2 1 2 3 4 5 5 1 1 2 -4 -1 5 | 15 7 |