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

Вам дан массив $$$a$$$ состоящий из $$$n$$$ целых чисел. Красота массива – это максимальная сумма какого-то последовательного подотрезка этого массива (этот подотрезок может быть пустым). Например красота массива [10, -5, 10, -4, 1] равна 15, а красота массива [-3, -5, -1] равна 0.

Вы можете выбрать не более одного последовательного подотрезка массива $$$a$$$ и домножить все элементы этого подотрезка на $$$x$$$. Вы хотите максимизировать красоту массива после применения такой операции.

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

Первая строка содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 3 \cdot 10^5, -100 \le x \le 100$$$) — длина массива $$$a$$$ и число $$$x$$$ соответственно.

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

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

Выведите одно число — максимальную красоту массива $$$a$$$ после не более одного домножения непрерывного подотрезка этого массива на $$$x$$$.

Примеры
Входные данные
5 -2
-3 8 -2 1 -6
Выходные данные
22
Входные данные
12 -3
1 3 3 7 1 3 3 7 1 3 3 7
Выходные данные
42
Входные данные
5 10
-1 -2 -3 -4 -5
Выходные данные
0
Примечание

В первом тестовом примере нужно домножить подотрезок [-2, 1, -6], после этого массив примет вид [-3, 8, 4, -2, 12] с красотой 22 ([-3, 8, 4, -2, 12]).

Во втором примере нам не нужно домножать какой-либо подотрезок массива вообще.

В третьем тестовом примере независимо от того, какой подотрезок мы домножим, красота массива будет равна 0.