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