D. Ciel и доска
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У лисы 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 в правом нижнем углу. Тогда все числа станут положительными.