| Codeforces Round 190 (Div. 1) |
|---|
| Закончено |
У лисы Ciel есть доска, на доске нарисована таблица из n строк и n столбцов, в каждой ячейке записано по целому числу.
Известно, что число n нечетное. Введем обозначение 
. Лиса Ciel может осуществить следующую операцию несколько раз: выбрать подтаблицу размера x строк на x столбцов, затем умножить все числа в ней на -1.
Найдите максимальную сумму чисел на доске, которую может получить Ciel.
В первой строке записано целое число n, (1 ≤ n ≤ 33, и n — нечетное число) — размер таблицы.
В каждой из следующих n строк записано n целых чисел — числа, записанные на доске. Каждое число не превышает по модулю 1000.
Выведите единственное целое число: максимальную достижимую сумму чисел на доске.
3
-1 -1 1
-1 1 -1
1 -1 -1
9
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
В первом тесте можно применить операцию дважды: сперва на подтаблице размера 2 × 2 в левом верхнем углу, затем — на подтаблице размера 2 × 2 в правом нижнем углу. Тогда все числа станут положительными.
