Вам дан массив \(a\) состоящий из \(n\) целых чисел. Красота массива – это максимальная сумма какого-то последовательного подотрезка этого массива (этот подотрезок может быть пустым). Например красота массива [10, -5, 10, -4, 1] равна 15, а красота массива [-3, -5, -1] равна 0.
Вы можете выбрать не более одного последовательного подотрезка массива \(a\) и домножить все элементы этого подотрезка на \(x\). Вы хотите максимизировать красоту массива после применения такой операции.
Выходные данные
Выведите одно число — максимальную красоту массива \(a\) после не более одного домножения непрерывного подотрезка этого массива на \(x\).
Примечание
В первом тестовом примере нужно домножить подотрезок [-2, 1, -6], после этого массив примет вид [-3, 8, 4, -2, 12] с красотой 22 ([-3, 8, 4, -2, 12]).
Во втором примере нам не нужно домножать какой-либо подотрезок массива вообще.
В третьем тестовом примере независимо от того, какой подотрезок мы домножим, красота массива будет равна 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 -2
-3 8 -2 1 -6
|
22
|
|
2
|
12 -3
1 3 3 7 1 3 3 7 1 3 3 7
|
42
|
|
3
|
5 10
-1 -2 -3 -4 -5
|
0
|