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 完成