CF1684D.Traps

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.

共有 $n$ 个陷阱，编号从 $1$ 到 $n$。你将按顺序依次经过这些陷阱。第 $i$ 个陷阱对你造成 $a_i$ 点基础伤害。

你也可以选择跳过某个陷阱而不经过它。你最多可以跳过 $k$ 个陷阱。若你跳过某个陷阱，则该陷阱不会对你造成任何伤害。但存在一条额外规则：每当你跳过一个陷阱，其后所有未跳过的陷阱所造成的伤害均增加 $1$（即额外伤害）。

注意：若你跳过某个陷阱，则你不会受到该陷阱的任何伤害（既无基础伤害，也无额外伤害）。此外，额外伤害具有叠加性；例如，若你经过第 $i$ 个陷阱（其基础伤害为 $a_i$），且此前已跳过了 $3$ 个陷阱，则你将受到 $(a_i + 3)$ 点伤害。

你需要求出：在最多跳过 $k$ 个陷阱的前提下，所能承受的最小总伤害。

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$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le n$），分别表示陷阱的数量以及允许的跳跃次数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示所有陷阱的基础伤害值。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

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.

对于每个测试用例，输出一个整数——即在最多跳过 $k$ 个陷阱的前提下，所能受到的最小总伤害。

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$.

在第一个测试用例中，允许跳过所有陷阱，造成 $0$ 点伤害。

在第二个测试用例中，共有 $5$ 种跳过部分陷阱的方式：

1. 不跳过任何陷阱。

   总伤害：$5 + 10 + 11 + 5 = 31$。

2. 跳过第 $1$ 个陷阱。

   总伤害：$\underline{0} + (10 + 1) + (11 + 1) + (5 + 1) = 29$。

3. 跳过第 $2$ 个陷阱。

   总伤害：$5 + \underline{0} + (11 + 1) + (5 + 1) = 23$。

4. 跳过第 $3$ 个陷阱。

   总伤害：$5 + 10 + \underline{0} + (5 + 1) = 21$。

5. 跳过第 $4$ 个陷阱。

   总伤害：$5 + 10 + 11 + \underline{0} = 26$。

为获得最小伤害，需跳过第 $3$ 个陷阱，因此答案为 $21$。

在第三个测试用例中，最优策略是跳过第 $1$、$3$、$4$、$5$、$7$ 个陷阱：

总伤害：$0 + (2 + 1) + 0 + 0 + 0 + (2 + 4) + 0 = 9$。