Вам дана прямоугольная сетка с \(n\) строками и \(m\) столбцами. В ячейке, расположенной на \(i\)-й строке сверху и \(j\)-м столбце слева, записано значение \(a_{ij}\).
Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
- Выберите любые две соседние ячейки и умножьте значения в них на \(-1\). Две ячейки называются соседними, если они имеют общую сторону.
Обратите внимание, что одну и ту же ячейку можно использовать несколько раз при различных операциях.
Вас интересует \(X\), сумма всех чисел в сетке.
Какое максимально возможное \(X\) вы можете получить с помощью данных операций?
Выходные данные
Для каждого набора входных данных выведите одно целое \(X\) — максимально возможную сумму всех значений в сетке после применения операции столько раз, сколько вам нужно.
Примечание
В первом наборе входных данных всегда будет как минимум одна \(-1\), так что ответ равен \(2\).
Во втором наборе входных данных можно шесть раз использовать операцию для элементов, соседних по горизонтали, и сделать все числа неотрицательными. Так что ответ: \(2\times 1 + 3\times2 + 3\times 3 + 2\times 4 + 1\times 5 = 30\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 2
-1 1
1 1
3 4
0 -1 -2 -3
-1 -2 -3 -4
-2 -3 -4 -5
|
2
30
|