310629: CF1862E. Kolya and Movie Theatre

E. Kolya and Movie Theatretime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExampleInput

6
5 2 2
3 2 5 4 6
4 3 2
1 1 1 1
6 6 6
-82 45 1 -77 39 11
5 2 2
3 2 5 4 8
2 1 1
-1 2
6 3 2
-8 8 -2 -1 9 0

Output

2
0
60
3
0
7

Note

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

题目大意：
Kolya发现他的城市即将开业一家新的电影院，这家电影院将在接下来的n天内每天上映一部新电影。具体来说，第1到第n天，电影院将分别上映第1到第n部电影，每部电影都有一个娱乐价值a_i。但是，Kolya不去电影院的每一天，下一部电影的娱乐价值都会减少d*cnt，其中d是一个预定值，cnt是自上次访问电影院以来的天数。已知Kolya在电影院开业前一天（即第0天）去了另一家电影院。所以，如果我们在第i天第一次去电影院，那么自上次访问电影院以来的天数cnt就是i。Kolya只能看最多m部电影，我们需要帮助他制定一个计划，使他能获得的电影的总娱乐价值最大化。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含三个整数n、m和d（1≤n≤2*10^5，1≤m≤n，1≤d≤10^9）。
- 每个测试用例的第二行包含n个整数a_1,a_2,…,a_n（-10^9≤a_i≤10^9），表示电影的娱乐价值。

输出：
- 对于每个测试用例，输出一个整数，表示Kolya可以获得的最大总娱乐价值。题目大意： Kolya发现他的城市即将开业一家新的电影院，这家电影院将在接下来的n天内每天上映一部新电影。具体来说，第1到第n天，电影院将分别上映第1到第n部电影，每部电影都有一个娱乐价值a_i。但是，Kolya不去电影院的每一天，下一部电影的娱乐价值都会减少d*cnt，其中d是一个预定值，cnt是自上次访问电影院以来的天数。已知Kolya在电影院开业前一天（即第0天）去了另一家电影院。所以，如果我们在第i天第一次去电影院，那么自上次访问电影院以来的天数cnt就是i。Kolya只能看最多m部电影，我们需要帮助他制定一个计划，使他能获得的电影的总娱乐价值最大化。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含三个整数n、m和d（1≤n≤2*10^5，1≤m≤n，1≤d≤10^9）。 - 每个测试用例的第二行包含n个整数a_1,a_2,…,a_n（-10^9≤a_i≤10^9），表示电影的娱乐价值。 输出： - 对于每个测试用例，输出一个整数，表示Kolya可以获得的最大总娱乐价值。