Serval刚刚找到了一家回转寿司自助餐厅。回转寿司的意思是餐厅里有一条传送带,将一盘盘寿司送到顾客薮猫面前。
在这家餐厅中,每个盘子恰好包含 $$$k$$$ 块寿司,并且第 $$$i$$$ 个盘子有一个 美味 $$$d_i$$$。 Serval 将在这家餐厅用餐 $$$n$$$ 分钟,并且在 $$$n$$$ 分钟内,他必须吃完 全部 他从腰带上取出的寿司片。
将未吃完的寿司的计数器表示为$$$r$$$。最初,$$$r=0$$$。在第 $$$i$$$ 分钟($$$1\leq i\leq n$$$)内,只有第 $$$i$$$ 盘寿司会送到 Serval 面前,而他可以这样做 一 以下内容:
- 拿第 $$$i$$$ 盘寿司(其 美味 是来自腰带的 $$$d_i$$$),$$$r$$$ 将增加 $$$k$$$;
- 吃掉之前从腰带上拿走的一块未吃的寿司,$$$r$$$将减少$$$1$$$。请注意,只有 $$$r \gt 0$$$ 时才可以执行此操作;
- 或者,什么都不做,$$$r$$$ 将保持不变。
请注意,在 $$$n$$$ 分钟之后,$$$r$$$ 的值 必须 为 $$$0$$$。
Serval 希望最大化 美味 他拿走的所有车牌中的 。帮他找出来吧!
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\leq k \lt n\leq 2\cdot 10^5$$$) — 用餐的分钟数和每个盘子中寿司的数量。
第二行包含 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n$$$ ($$$1\leq d_i\leq 10^9$$$) — 每个板的 美味 。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 的最大可能总和 美味 他拿走的所有车牌中的 薮猫拿走的所有盘子。
示例
输入复制
55 23 6 4 1 27 13 1 4 1 5 9 24 34 3 2 16 21 3 5 2 4 66 11000000000 1 1000000000 1 1000000000 1
输出复制
6 16 4 6 3000000000
注意
在第一个测试用例中,可以证明 Serval 最多可以吃掉一盘寿司。由于第二盘寿司的分量最大 美味 $$$6$$$在所有盘子中,他会在第二分钟从腰带上取出它,然后在接下来的$$$2$$$分钟内吃掉它。
| 分钟 | $$$1$$$ | $$$2$$$ | $$$3$$$ | $$$4$$$ | $$$5$$$ |
| 行动 | — | 采取 | 吃 | 吃 | — |
| 行动后$$$r$$$ | $$$0$$$ | $$$2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ |
| 美味 获得 | $$$0$$$ | $$$6$$$ | $$$6$$$ | $$$6$$$ | $$$6$$$ |
在第二个测试用例中,可以证明薮猫吃完第一盘、第三盘和第六盘寿司是最优的。的总和 这些车牌的 美味 他拿走的所有车牌中的 为 $$$3 + 4 + 9 = 16$$$。
| 分钟 | $$$1$$$ | $$$2$$$ | $$$3$$$ | $$$4$$$ | $$$5$$$ | $$$6$$$ | $$$7$$$ |
| 行动 | 采取 | 吃 | 采取 | 吃 | — | 采取 | 吃 |
| 行动后$$$r$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ |
| 美味 获得 | $$$3$$$ | $$$3$$$ | $$$7$$$ | $$$7$$$ | $$$7$$$ | $$$16$$$ | $$$16$$$ |