Дан массив \(a\), состоящий из \(n\) целых чисел, и множество \(B\), состоящее из \(m\) положительных целых чисел таких, что \(1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor\) при \(1\le i\le m\), где \(b_i\) — \(i\)-й элемент \(B\).
Вы можете выполнять следующую операцию с \(a\):
- Выбрать некоторый \(x\) такой, что \(x\) содержится в \(B\).
- Выбрать подмассив \(a\) размера \(x\) и умножить на \(-1\) каждый элемент этого подмассива. Формально, выбрать \(l\) и \(r\) такие, что \(1\leq l\leq r \leq n\) и \(r-l+1=x\), и затем присвоить \(a_i:=-a_i\) для всех \(i\) таких, что \(l\leq i\leq r\).
Рассмотрим пример. Пусть \(a=[0,6,-2,1,-4,5]\) и \(B=\{1,2\}\):
- \([0,6,-2,-1,4,5]\) получится, если выбрать размер подмассива \(2\) и \(l=4\), \(r=5\).
- \([0,6,2,-1,4,5]\) получится, если после этого выбрать размер подмассива \(1\) и \(l=3\), \(r=3\).
Найдите максимальную сумму \(\sum\limits_{i=1}^n {a_i}\), которую можно получить, применяя данную операцию неограниченное количество раз (возможно ноль).
Выходные данные
Для каждого набора входных данных напечатайте одно целое число — максимальную сумму всех \(a_i\), которую можно получить, применяя описанную операцию неограниченное количество раз.
Примечание
В первом наборе входных данных можно проделать операции с \(x=1\), \(l=3\), \(r=3\) и \(x=1\), \(l=5\), \(r=5\), и получить массив \([0, 6, 2, 1, 4, 5]\)
Во втором наборе можно проделать операцию с \(x=2\), \(l=2\), \(r=3\), получив массив \([1, 1, -1, -1, 1, -1, 1]\), затем проделать операцию с \(x=2\), \(l=3\), \(r=4\), получив массив \([1, 1, 1, 1, 1, -1, 1]\). Не существует способа получить сумму, большую \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 2
0 6 -2 1 -4 5
1 2
7 1
1 -1 1 -1 1 -1 1
2
5 1
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000
1
|
18
5
5000000000
|