Фермер Джон хочет сфотографировать своих пасущихся коров, чтобы повесить эту фотографию на стене. Пастбище представлено решёткой из N * N ячеек (как шахматная доска размером N×N) (2≤N≤1000). ФД хочет, чтобы коровы были распределены по пастбищу с выполнением следующих правил:
Никакие две коровы не могут находится в одной и той же ячейке.
Каждая подрешётка размером 2×2 (всего таких подрешёток (N−1)×(N−1)) должна содержать ровно 2 коровы
Например, такое размещение соотвествует правилам:
CCC
...
CCC
А такое размещение - нет
C.C
.C.
C..
поскольку 2×2 регион в правом нижем углу содержит только одну корову.
Других ограничений нет. Вы можете считать, что у ФД есть бесконечное количество коров.
Некоторые ячейки более предпочтительный для ФД, нежели другие. В частности, ФД считает. что если корова размещена в ячейке (i,j), красота фотографии увеличивается на a
ij (0≤a
ij≤1000) единиц.
Определите максимально возможную красоту корректного размещения коров.
Входные данные
Первая строка содержит число N. Каждая из следующих N строк содержит по N целых чисел. j-ое число в i-ой строке сверху есть значение a
ij.
Выходные данные
Выведите одно целое число - максимально возможную красоту результирующего фото.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3
|
22 |
В этом примере максимальная красота может быть достигнута следующим размещением:
CC..
..CC
CC..
..CC
Красота этого размещения 3+3+3+1+3+3+3+3=22. |