# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Limits
2s, 512 MB

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 ≤ 10 ^{5} )** 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 **-10 ^{9} ≤ a_{i} ≤ 10^{9}**

**Constraints**

**1 ≤ T ≤ 10****1 ≤ N ≤ 10**^{5}**1 ≤ K ≤ 10**^{9}**-10**^{9}≤ a_{i}≤ 10^{9}

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 |

Login to submit