CF1862E Kolya and Movie Theatre

最近，Kolya 得知他所在的城市即将开设一家新的电影院，这家电影院将在接下来的 $n$ 天内每天上映一部新电影。因此，在第 $1 \le i \le n$ 天，电影院将首映第 $i$ 部电影。同时，Kolya 还得知了电影的排片表，并为每部电影分配了一个娱乐价值，记为 $a_i$。 然而，Kolya 距离上一次去电影院的时间越长，下一部电影的娱乐价值就会减少得越多。这个减少量等于 $d \cdot cnt$，其中 $d$ 是一个预定的值，$cnt$ 是自上次去电影院以来经过的天数。已知 Kolya 在新电影院开业的前一天（即第 $0$ 天）去过另一家电影院。因此，如果他第一次在第 $i$ 天去新电影院，那么 $cnt$——自上次去电影院以来的天数——就等于 $i$。 例如，如果 $d = 2$ 且 $a = [3, 2, 5, 4, 6]$，那么如果选择在第 $1$ 天和第 $3$ 天去看电影，第 $1$ 天的 $cnt$ 为 $1 - 0 = 1$，第 $3$ 天的 $cnt$ 为 $3 - 1 = 2$，因此总娱乐价值为 $a_1 - d \cdot 1 + a_3 - d \cdot 2 = 3 - 2 \cdot 1 + 5 - 2 \cdot 2 = 2$。 不幸的是，Kolya 最多只能去看 $m$ 部电影。请帮助他制定一个观影计划，使他能获得的总娱乐价值最大。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。接下来是每组测试用例的描述。 每组测试用例的第一行包含三个整数 $n$、$m$ 和 $d$（$1 \le n \le 2 \cdot 10^5$，$1 \le m \le n$，$1 \le d \le 10^9$）。 每组测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$），表示每部电影的娱乐价值。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出一个整数，表示 Kolya 能获得的最大总娱乐价值。

第一个测试用例的解释见题目描述。 第二个测试用例中，最优选择是不去看任何电影。 第三个测试用例中，最优选择是在第 $2$、$3$、$5$、$6$ 天去看电影，因此总娱乐价值为 $45 - 6 \cdot 2 + 1 - 6 \cdot 1 + 39 - 6 \cdot 2 + 11 - 6 \cdot 1 = 60$。 由 ChatGPT 4.1 翻译