У лисы Ciel есть доска, на доске нарисована таблица из n строк и n столбцов, в каждой ячейке записано по целому числу.
Известно, что число n нечетное. Введем обозначение 
. Лиса Ciel может осуществить следующую операцию несколько раз: выбрать подтаблицу размера x строк на x столбцов, затем умножить все числа в ней на -1.
Найдите максимальную сумму чисел на доске, которую может получить Ciel.
Выходные данные
Выведите единственное целое число: максимальную достижимую сумму чисел на доске.
Примечание
В первом тесте можно применить операцию дважды: сперва на подтаблице размера 2 × 2 в левом верхнем углу, затем — на подтаблице размера 2 × 2 в правом нижнем углу. Тогда все числа станут положительными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
-1 -1 1
-1 1 -1
1 -1 -1
|
9
|
|
2
|
5
-2 0 0 0 -2
0 -2 0 -2 0
0 0 -2 0 0
0 -2 0 -2 0
-2 0 0 0 -2
|
18
|