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

ФД хоче, щоб корови були розподілені по пасовищу з виконанням наступних правил:

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

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

CCC
...
CCC

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

C.C
.C.
C.

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

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

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

Формат вхідних даних

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

Формат вихідних даних

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

Приклад вхідних даних

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\).

ОЦІНЮВАННЯ:

• У тестах 2-4 \(N \le 4\).
• У тестах 5-10 \(N\le 10\).
• У тестах 11-20 \(N \le 1000\).