← 返回题目列表

Codeforces · 1862/E

E. Kolya 和电影院

中文机器翻译题面 查看原题

最近,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$$$ 和 $$$cnt$$$当天 $$$3$$$ 的价值将为 $$$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 可以获得的最大总娱乐价值。

示例

输入 #1

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

输出 #1

2
0
60
3
0
7

注意

第一个测试用例在问题陈述中进行了解释。

在第二个测试用例中,最好不要观看任何电影。

在第三个测试用例中,最好访问编号为 $$$2$$$、$$$3$$$、$$$5$$$、$$$6$$$ 的电影,因此访问电影的总娱乐价值将为 $$$45 - 6 \cdot 2 + 1 - 6 \cdot 1 + 39 - 6 \cdot 2 + 11 - 6 \cdot 1 = 60$$$。