E. Коля и кинотеатр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Коля узнал, что скоро в его городе откроется новый кинотеатр, который будет показывать новый фильм каждый день на протяжении $$$n$$$ дней. Так, в день номер $$$1 \le i \le n$$$, кинотеатр покажет премьеру $$$i$$$-го фильма. Коля узнал расписание фильмов и сопоставил каждому фильму его интересность — целую величину $$$a_i$$$.

Однако даже самые интересные фильмы не будут казаться такими, если фильмы долго не смотреть, поэтому интересность очередного фильма снизится на $$$d \cdot cnt$$$, где $$$d$$$ — заранее определенная величина, а $$$cnt$$$ — кол-во дней с последнего посещения кинотеатра. Также известно, что Коля успел посетить другой кинотеатр за день до открытия нового — в день номер $$$0$$$. Так, если мы впервые посетим кинотеатр в день с номером $$$i$$$, то $$$cnt$$$ — кол-во дней с последнего посещения кинотеатра будет равно $$$i$$$.

Так, например, если $$$d = 2$$$, а $$$a = [3, 2, 5, 4, 6]$$$, то посетив фильмы с номерами $$$1$$$ и $$$3$$$, значение $$$cnt$$$ для дня номер $$$1$$$ будет равно $$$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$$$.

К несчастью, у Коли есть время только на то, чтобы посетить не более $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите единственное число — максимальную суммарную интересность просмотренных фильмов.

Пример
Входные данные
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 \cdot 2 + 1 - 6 \cdot 1 + 39 - 6 \cdot 2 + 11 - 6 \cdot 1 = 60$$$.