B. Удалить и сконкатенировать
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ из $$$n$$$ целых чисел. Ваш начальный счёт равен $$$0$$$.

Вы можете выполнять следующие два типа операций любое количество раз пока массив не станет пустым:

  • Выберите один элемент. Прибавьте его значение к вашему счёту и удалите его из массива.
  • Выберите два соседних элемента. Прибавьте максимум из их значений к вашему счёту и удалите оба элемента из массива. (Для этой операции в массиве должно быть как минимум $$$2$$$ элемента.)

После каждой операции оставшиеся части элементы массива конкатенируются без изменения их относительного порядка.

Также дано целое число $$$c$$$, которое обозначает стоимость выполнения одной операции. Каждый раз, когда вы выполняете операцию (независимо от её типа), $$$c$$$ вычитается из вашего счёта.

Найдите максимальный возможный итоговый счёт, которого вы можете добиться.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$c$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le c \le 10^9$$$), обозначающие длину $$$a$$$ и стоимость выполнения одной операции соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$), обозначающих элементы $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите целое число, обозначающее максимальный возможный счёт, которого вы можете добиться.

Пример
Входные данные
5
1 0
-1
3 0
1 3 1
3 2
1 3 1
6 6
3 1 4 1 5 9
4 1000000000
-1000000000 -1000000000 -1000000000 -1000000000
Выходные данные
-1
5
0
0
-4000000000
Примечание

В первом наборе входных данных ваш единственный возможный выбор — выполнить первую операцию один раз. Ваш счёт равен $$$a_1-c=-1-0=-1$$$.

Во втором наборе входных данных одна из оптимальных последовательностей операций такая:

  • Выберите $$$3$$$. Ваш счёт становится $$$0+3-0=3$$$, а массив становится $$$[1,1]$$$.
  • Выберите первую $$$1$$$. Ваш счёт становится $$$3+1-0=4$$$, а массив становится $$$[1]$$$.
  • Выберите $$$1$$$. Ваш счёт становится $$$4+1-0=5$$$, а массив становится пустым.

В третьем наборе входных данных одна из оптимальных последовательностей операций такая:

  • Выберите $$$3$$$ и вторую $$$1$$$. Ваш счёт становится $$$0+\max(3,1)-2=1$$$, а массив становится $$$[1]$$$.
  • Выберите $$$1$$$. Ваш счёт становится $$$1+1-2=0$$$, а массив становится пустым.