有 $$$n$$$ 陷阱,编号从 $$$1$$$ 到 $$$n$$$。您将按顺序一一浏览它们。第 $$$i$$$ 个陷阱对你造成 $$$a_i$$$ 基础伤害。
你可以跳过陷阱,而不是穿过陷阱。您最多可以跳过 $$$k$$$ 个陷阱。如果你跳过陷阱,它不会对你造成任何伤害。但还有一条附加规则:如果你跳过陷阱,所有下一个陷阱的伤害都会增加$$$1$$$(这是额外伤害)。
请注意,如果你跳过陷阱,你不会受到任何伤害(既不是基础伤害,也不是额外伤害)。此外,额外伤害会叠加,例如,如果您穿过陷阱 $$$i$$$ 且基础伤害为 $$$a_i$$$,并且您已经跳过了 $$$3$$$ 陷阱,您将获得 $$$(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$$$ 陷阱,则可能获得的最小总伤害。
示例
输入 #1
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
输出 #1
0 21 9 6 0
注意
在第一个测试用例中,它被允许跳过所有陷阱并受到 $$$0$$$ 伤害。
在第二个测试用例中,有 $$$5$$$ 方法可以跳过一些陷阱:
1. 不要跳过任何陷阱。总伤害:$$$5 + 10 + 11 + 5 = 31$$$。
2. 跳过$$$1$$$-st陷阱。总伤害:$$$\underline{0} + (10 + 1) + (11 + 1) + (5 + 1) = 29$$$。
3. 跳过$$$2$$$-nd陷阱。总伤害:$$$5 + \underline{0} + (11 + 1) + (5 + 1) = 23$$$。
4. 跳过$$$3$$$-rd陷阱。总伤害:$$$5 + 10 + \underline{0} + (5 + 1) = 21$$$。
5. 跳过第 $$$4$$$ 个陷阱。总伤害:$$$5 + 10 + 11 + \underline{0} = 26$$$。
为了获得最小的伤害,需要跳过 $$$3$$$-rd 陷阱,所以答案是 $$$21$$$。
在第三个测试用例中,最好跳过陷阱 $$$1$$$、$$$3$$$、$$$4$$$、$$$5$$$、$$$7$$$:
总伤害:$$$0 + (2 + 1) + 0 + 0 + 0 + (2 + 4) + 0 = 9$$$。