Розподілені#11200

Розподілені

1 секунда

128 мегабайтів

Складна

Фермер Джон хоче сфотографувати своїх корів на пасовищі, щоб повісити цю фотографію на стіні. Пасовище представлено решіткою розміром $n \times n$ n \times n клітинок (як шахова дошка розміром $n \times n$ n \times n). Фермер Джон прагне розмістити корів на пасовищі, дотримуючись таких правил:

Жодні дві корови не можуть перебувати в одній і тій же клітинці.
Кожна підрешітка розміром $2 \times 2$ 2 \times 2 (всього таких підрешіток $(n - 1) \times (n - 1)$ (n - 1) \times (n - 1)) повинна містити рівно $2$ корови.

Наприклад, таке розміщення відповідає правилам:

CCC
...
CCC

А таке розміщення - ні:

C.C
.C.
C..

оскільки $2 \times 2$ 2 \times 2 регіон у правому нижньому куті містить лише одну корову.

Інших обмежень немає. Ви можете вважати, що у Фермера Джона є безкінечна кількість корів.

Деякі клітинки більш бажані для Фермера Джона, ніж інші. Зокрема, він вважає, що якщо корова розміщена в клітинці $(i, j)$ , краса фотографії збільшується на $a_{ij}$ a_{ij} ( $0 \leq a_{ij} \leq 1000$ 0 \le a_{ij} \le 1000) одиниць.

Визначте максимально можливу красу коректного розміщення корів.

Вхідні дані

Перша стрічка містить число $n$ ( $2 \leq n \leq 1000$ 2 \le n \le 1000). Кожна з наступних $n$ стрічок містить по $n$ цілих чисел. $j$ -е число в $i$ -ій стрічці зверху є значенням $a_{ij}$ a_{ij}.

Вихідні дані

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

Приклади

Приклад 1

Примітка

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

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

Краса цього розміщення $3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22$ 3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22.