A16093 | 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.

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

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