时序能量采集计划

题目描述

在未来城市中，存在一条由时间节点构成的能量通道。 在接下来的 n 天里，第 i 天会在时间节点 i 生成一个一次性可采集的能量核心，其基础能量值为 $a_i$。

工程师需要前往这些节点采集能量，但存在以下规则：

• 工程师不是每天都能出发，最多只能进行 m 次采集行动；
• 每次采集都会受到“时间衰减”影响： 若上一次采集发生在第 x 天，本次采集发生在第 y 天（y > x）， 则本次采集的能量会减少$$d \times (y - x)$$
• 在时间节点系统启动之前（记作第 0 天），工程师已经完成过一次采集行为。

举个例子，n = 5, m = 2, d = 2，a = [3, 2, 5, 4, 6]，如果选择第 1 天和第 3 天进行采集：第 1 天采集时，时间衰减为 $d \times (1-0) = 2$，获得能量 $3 - 2$；第 3 天采集时，时间衰减为 $d \times (3 - 1) = 4$，获得能量 $5 - 4$。总能量为 $(3 - 2) + (5 - 4) = 2$。

因此：

• 如果第一次采集发生在第 i 天，时间衰减为 $d \times i$；
• 若依次在第 $i_1, i_2, \dots, i_k$ 天采集，则总获得能量为 $\sum_{j=1}^{k} a_{i_j}$ 减去 $d$ 倍的 $\sum_{j=1}^{k} (i_j - i_{j-1})$，其中 $i_0 = 0$。

请你帮助工程师制定采集计划，在 最多进行 m 次采集 的前提下，使得最终获得的总能量最大。

输入格式

输入包含多组测试用例。第一行输入一个整数 $t$（$1 \leq t \leq 10^{4}$），表示测试用例的数量。接下来是各组测试用例的详细描述。

每组测试用例的第一行包含三个整数 $n$、$m$、$d$（$1 \leq n \leq 2 \times 10^{5}$，$1 \leq m \leq n$，$1 \leq d \leq 10^{9}$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^{9} \leq a_i \leq 10^{9}$），分别对应每一天的基础能量值。

保证所有测试用例的n之和不超过$2 \times 10^{5}$。

输出格式

对于每组测试用例，输出一个整数，表示工程师能够获得的最大总能量。

样例 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

2
0
60
3
0
7

提示

第一个测试用例的解释已在题目描述中给出。 第二个测试用例的最优选择是不采集任何能量核心。 第三个测试用例的最优选择是采集第2、3、5、6天的能量核心，总能量计算为45−6×2 + 1−6×1 + 39−6×2 + 11−6×1 = 60。