CF1862E.Kolya and Movie Theatre

Recently, Kolya found out that a new movie theatre is going to be opened in his city soon, which will show a new movie every day for $n$ days. So, on the day with the number $1 \le i \le n$, the movie theatre will show the premiere of the $i$-th movie. Also, Kolya found out the schedule of the movies and assigned the entertainment value to each movie, denoted by $a_i$.

However, the longer Kolya stays without visiting a movie theatre, the larger the decrease in entertainment value of the next movie. That decrease is equivalent to $d \cdot cnt$, where $d$ is a predetermined value and $cnt$ is the number of days since the last visit to the movie theatre. It is also known that Kolya managed to visit another movie theatre a day before the new one opened — the day with the number $0$. So if we visit the movie theatre the first time on the day with the number $i$, then $cnt$ — the number of days since the last visit to the movie theatre will be equal to $i$.

For example, if $d = 2$ and $a = [3, 2, 5, 4, 6]$, then by visiting movies with indices $1$ and $3$, $cnt$ value for the day $1$ will be equal to $1 - 0 = 1$ and $cnt$ value for the day $3$ will be $3 - 1 = 2$, so the total entertainment value of the movies will be $a_1 - d \cdot 1 + a_3 - d \cdot 2 = 3 - 2 \cdot 1 + 5 - 2 \cdot 2 = 2$.

Unfortunately, Kolya only has time to visit at most $m$ movies. Help him create a plan to visit the cinema in such a way that the total entertainment value of all the movies he visits is maximized.

最近，科里亚得知他的城市即将新开一家电影院，该影院将在接下来的 $n$ 天内每天上映一部新电影。因此，在编号为 $1 \le i \le n$ 的第 $i$ 天，该影院将上映第 $i$ 部电影的首映式。此外，科里亚还了解了所有电影的排片表，并为每部电影赋予了一个娱乐价值，记为 $a_i$。

然而，科里亚距离上一次观影的时间越长，下一部电影的娱乐价值衰减就越严重。该衰减值等于 $d \cdot cnt$，其中 $d$ 是一个预先给定的常数，$cnt$ 是自上一次观影以来所经过的天数。已知科里亚在这家新影院开业前一天（即编号为 $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$。

不幸的是，科里亚最多只能观看 $m$ 部电影。请帮他制定一个观影计划，使得他所观看的所有电影的总娱乐价值最大化。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $d$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le n$, $1 \le d \le 10^9$).

The second line of each set of input data contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the entertainment values of the movies.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer — the maximum total entertainment value that Kolya can get.

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

The first test case is explained in the problem statement.

In the second test case, it is optimal not to visit any movies.

In the third test case, it is optimal to visit movies with numbers $2$, $3$, $5$, $6$, so the total entertainment value of the visited movies will be $45 - 6 \cdot 2 + 1 - 6 \cdot 1 + 39 - 6 \cdot 2 + 11 - 6 \cdot 1 = 60$.

第一个测试用例已在题目描述中说明。

在第二个测试用例中，最优策略是不观看任何电影。

在第三个测试用例中，最优策略是观看编号为 $2$、$3$、$5$、$6$ 的电影，因此所观看电影的总娱乐值为 $45 - 6 \cdot 2 + 1 - 6 \cdot 1 + 39 - 6 \cdot 2 + 11 - 6 \cdot 1 = 60$。