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