Фермер Джон хочет сфотографировать своих пасущихся коров, чтобы повесить эту фотографию на стене. Пастбище представлено решёткой из n * n ячеек (как шахматная доска размером n * n). ФД хочет, чтобы коровы были распределены по пастбищу с выполнением следующих правил:

• Никакие две коровы не могут находится в одной и той же ячейке.
• Каждая подрешётка размером 2 * 2 (всего таких подрешёток (n − 1 ) * (n − 1)) должна содержать ровно 2 коровы

Например, такое размещение соотвествует правилам:

CCC
...
CCC

А такое размещение - нет

C.C
.C.
C..

поскольку 2 * 2 регион в правом нижем углу содержит только одну корову.

Других ограничений нет. Вы можете считать, что у ФД есть бесконечное количество коров.

Некоторые ячейки более предпочтительный для ФД, нежели другие. В частности, ФД считает, что если корова размещена в ячейке (i, j), красота фотографии увеличивается на aij (0 ≤ aij ≤ 1000) единиц.

Определите максимально возможную красоту корректного размещения коров.

Входные данные

Первая строка содержит число n (2 ≤ n ≤ 1000). Каждая из следующих n строк содержит по n целых чисел. j-ое число в i-ой строке сверху есть значение aij.

Выходные данные

Выведите одно целое число - максимально возможную красоту результирующего фото.

Пример

В этом примере максимальная красота может быть достигнута следующим размещением:

CC..
..CC
CC..
..CC

Красота этого размещения 3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22.