← 返回题目列表

Codeforces · 2085/D

D. 薮猫和回转寿司自助餐

中文机器翻译题面 查看原题

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

输出

对于每个测试用例,打印一个整数 - 的最大可能总和 美味 他拿走的所有车牌中的 薮猫拿走的所有盘子。

示例

输入
复制

5
5 2
3 6 4 1 2
7 1
3 1 4 1 5 9 2
4 3
4 3 2 1
6 2
1 3 5 2 4 6
6 1
1000000000 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$$$