CF1684D Traps

有 $n$ 个陷阱，编号从 $1$ 到 $n$。你需要依次通过这些陷阱。第 $i$ 个陷阱会对你造成 $a_i$ 的基础伤害。 你可以选择跳过某些陷阱，但最多只能跳过 $k$ 个陷阱。如果你跳过了一个陷阱，那么该陷阱不会对你造成任何伤害。但有一个额外的规则：每当你跳过一个陷阱，之后所有陷阱的伤害都会增加 $1$（即额外伤害）。 注意，如果你跳过了某个陷阱，你不会受到任何伤害（既不会受到基础伤害，也不会受到额外伤害）。而且，额外伤害是可以叠加的。例如，如果你已经跳过了 $3$ 个陷阱，当你通过第 $i$ 个陷阱时，你会受到 $a_i + 3$ 的伤害。 请你计算，在最多允许跳过 $k$ 个陷阱的情况下，你能获得的最小总伤害是多少。

输入包含多组测试用例。第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示在最多允许跳过 $k$ 个陷阱的情况下，你能获得的最小总伤害。

在第一个测试用例中，可以跳过所有陷阱，受到的伤害为 $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$。 由 ChatGPT 4.1 翻译