Traps
Contest: Codeforces Round 792 (Div. 1 + Div. 2)
Difficulty rating: 1700
Tags: constructive algorithms, greedy, sortings

There are $$$n$$$ traps numbered from $$$1$$$ to $$$n$$$. You will go through them one by one in order. The $$$i$$$-th trap deals $$$a_i$$$ base damage to you.

Instead of going through a trap, you can jump it over. You can jump over no more than $$$k$$$ traps. If you jump over a trap, it does not deal any damage to you. But there is an additional rule: if you jump over a trap, all next traps damages increase by $$$1$$$ (this is a bonus damage).

Note that if you jump over a trap, you don't get any damage (neither base damage nor bonus damage). Also, the bonus damage stacks so, for example, if you go through a trap $$$i$$$ with base damage $$$a_i$$$, and you have already jumped over $$$3$$$ traps, you get $$$(a_i + 3)$$$ damage.

You have to find the minimal damage that it is possible to get if you are allowed to jump over no more than $$$k$$$ traps.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$) — the number of traps and the number of jump overs that you are allowed to make.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — base damage values of all traps.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case output a single integer — the minimal total damage that it is possible to get if you are allowed to jump over no more than $$$k$$$ traps.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case it is allowed to jump over all traps and take $$$0$$$ damage.

In the second test case there are $$$5$$$ ways to jump over some traps:

1. Do not jump over any trap.Total damage: $$$5 + 10 + 11 + 5 = 31$$$.
2. Jump over the $$$1$$$-st trap.Total damage: $$$\underline{0} + (10 + 1) + (11 + 1) + (5 + 1) = 29$$$.
3. Jump over the $$$2$$$-nd trap.Total damage: $$$5 + \underline{0} + (11 + 1) + (5 + 1) = 23$$$.
4. Jump over the $$$3$$$-rd trap.Total damage: $$$5 + 10 + \underline{0} + (5 + 1) = 21$$$.
5. Jump over the $$$4$$$-th trap.Total damage: $$$5 + 10 + 11 + \underline{0} = 26$$$.

To get minimal damage it is needed to jump over the $$$3$$$-rd trap, so the answer is $$$21$$$.

In the third test case it is optimal to jump over the traps $$$1$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$7$$$:

Total damage: $$$0 + (2 + 1) + 0 + 0 + 0 + (2 + 4) + 0 = 9$$$.

Example input:
5
4 4
8 7 1 4
4 1
5 10 11 5
7 5
8 2 5 15 11 2 8
6 3
1 2 3 4 5 6
1 1
7

Example output:
0
21
9
6
0

Editorial:
Firstly, let's notice that it is always better to use all $$$k$$$ jumps. If we jumped over less than $$$k$$$ traps then we can jump over the last trap and the total damage will be less.
Secondly, let's say that we immediately get $$$n - i$$$ damage if we jump over $$$i$$$-th trap. This way the first trap that we jump over will cause $$$k - 1$$$ damage more than it should (because of $$$k - 1$$$ traps that we jump over next), the second will cause $$$k - 2$$$ damage more, ..., the last one will cause $$$0$$$ damage more. So the total damage only increases by $$$\frac{k(k - 1)}{2}$$$ which does not depend on the traps that we choose. That's why the traps that we have to jump over in this problem are the same.
Now let's consider an array $$$b: b_i = a_i - (n - i)$$$. This array denotes the amount of damage we dodge if we jump over $$$i$$$-th trap (dodge $$$a_i$$$ because we don't take the trap's damage but get $$$n - i$$$ because of the immediate damage we take). Here a simple greedy works: let's just chose $$$k$$$ maximal values of this array, these will be the traps that we have to jump over so the total damage that we dodge is maximized. These traps will be the answer to the original problem.