D. Максимальный подмассив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$a_1, a_2, \dots, a_n$$$, состоящий из $$$n$$$ целых чисел. Также дано два целых числа $$$k$$$ и $$$x$$$.

Вы должны выполнить следующую операцию ровно один раз: прибавить $$$x$$$ к элементам на ровно $$$k$$$ различных позициях и вычесть $$$x$$$ на всех остальных.

Например, если $$$a = [2, -1, 2, 3]$$$, $$$k = 1$$$, $$$x = 2$$$, и мы выбрали увеличить первый элемент, тогда после применения операции $$$a = [4, -3, 0, 1]$$$.

Пусть $$$f(a)$$$ — максимальная сумма подмассива из $$$a$$$. Подмассив массива $$$a$$$ — это последовательная часть массива $$$a$$$, другими словами массив $$$a_i, a_{i + 1}, \dots, a_j$$$ для некоторых $$$1 \le i \le j \le n$$$. Пустой подмассив тоже рассматривается, его сумма равна $$$0$$$.

Пусть массив $$$a'$$$ будет массивом $$$a$$$ после применения вышеупомянутой операции. Примените операцию таким образом, чтобы $$$f(a')$$$ было максимально возможным, и выведите максимально возможное значение $$$f(a')$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$k$$$ и $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le \min(20, n)$$$; $$$-10^9 \le x \le 10^9$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно число — максимально возможное значение $$$f(a')$$$.

Пример
Входные данные
4
4 1 2
2 -1 2 3
2 2 3
-1 2
3 0 5
3 2 4
6 2 -8
4 -1 9 -3 7 -8
Выходные данные
5
7
0
44