CF2085D.Serval and Kaitenzushi Buffet

Serval 发现了一家回转寿司自助餐厅。回转寿司意味着餐厅内有一条传送带，将寿司盘依次传送到顾客 Serval 面前。

在这家餐厅中，每盘寿司恰好包含 $k$ 块寿司，第 $i$ 盘寿司的美味值为 $d_i$。Serval 将在这家餐厅用餐 $n$ 分钟，且在这 $n$ 分钟内必须吃完他从传送带上拿取的所有寿司块。

设未食用的已拿取寿司块计数器为 $r$。初始时 $r = 0$。在第 $i$ 分钟（$1 \leq i \leq n$），只有第 $i$ 盘寿司会被传送到 Serval 面前，他可以执行以下三种操作之一：

• 从传送带上拿取第 $i$ 盘寿司（其美味值为 $d_i$），此时 $r$ 增加 $k$；
• 食用之前从传送带上拿取的 1 块未食用寿司，此时 $r$ 减少 $1$（注意仅当 $r > 0$ 时可执行此操作）；
• 或不做任何操作，此时 $r$ 保持不变。

注意在 $n$ 分钟结束后，$r$ 的值必须为 $0$。

Serval 希望最大化他拿取的所有寿司盘的美味值之和。请帮助他计算这个最大值！

每个测试包含多个测试用例。第一行输入测试用例数 $t$（$1 \le t \le 10^4$）。接下来描述每个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq k < 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$。

对于每个测试用例，输出一个整数 —— Serval 拿取的所有寿司盘美味值的最大可能和。

第一个测试案例中，可以证明 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

翻译由 DeepSeek R1 完成