Description

Farmer John wants to take a photo of his cows grazing and hang it on the wall. The field can be represented as an $N$ by $N$ square grid (imagine an $N \times N$ chessboard), where $2 \leq N \leq 1000$. In Farmer John’s recent photos, his cows were too concentrated in one area of the field. This time, he wants to make sure his cows are spread out across the entire field, so he insists on the following rules:

• No two cows may be in the same cell.
• Every $2 \times 2$ submatrix (there are $(N-1) \times (N-1)$ of them) must contain exactly 2 cows.

For example, this placement is valid:

CCC
...
CCC

But this placement is invalid, because the bottom-right $2 \times 2$ square contains only 1 cow:

C.C
.C.
C..

There are no other restrictions. You may assume Farmer John has infinitely many cows (based on past experience, this seems to be true...).

Farmer John also prefers some cells to contain cows. Specifically, he believes that if a cow is placed in cell $(i, j)$, the beauty of the photo increases by $a_{ij}$ units ($0 \leq a_{ij} \leq 1000$).

Find the maximum total beauty over all valid cow placements.

Input Format

The first line contains $N$. The next $N$ lines each contain $N$ integers. From top to bottom, the $j$-th integer on the $i$-th line is the value of $a_{ij}$.

Output Format

Output one integer: the maximum beauty of the resulting photo.

4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3

22

Hint

In this sample, the maximum beauty can be achieved with the following placement:

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

The beauty of this placement is $3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22$.

Testdata properties:

• Test cases 2-4 satisfy $N \le 4$.
• Test cases 5-10 satisfy $N \le 10$.
• Test cases 11-20 satisfy $N \le 1000$.

Problem by: Hankai Zhang, Danny Mittal.

Translated by ChatGPT 5