Farmer John's Grazing Photo

Farmer John wants to take a picturesque photo of his cows grazing on a field. The field is represented as an $N \times N$ grid where $2 \leq N \leq 1000$.

He requires that the cow placement satisfies the following conditions:

• No two cows can occupy the same cell.
• Every $2 \times 2$ submatrix (there are $(N-1) \times (N-1)$ such submatrices) must contain exactly 2 cows.

Each cell $(i,j)$ has an associated beauty value $a_{ij}$ (with $0 \leq a_{ij} \leq 1000$). If a cow is placed in cell $(i,j)$, the beauty of the photo increases by $a_{ij}$ units.

Find a valid placement of cows that maximizes the total beauty. It turns out that there are only two possible patterns that satisfy the above conditions: one where cows are placed in cells with (i+j) mod 2 = 0 and the other where cows are placed in cells with (i+j) mod 2 = 1. You need to choose the one yielding the maximum total beauty.

inputFormat

The first line contains an integer $N$ ($2 \leq N \leq 1000$), the size of the grid.

Each of the next $N$ lines contains $N$ integers, where the $j$-th integer in the $i$-th line represents $a_{ij}$ ($0 \leq a_{ij} \leq 1000$), the beauty value of cell $(i,j)$.

outputFormat

Output a single integer, the maximum total beauty achievable by placing the cows according to the rules described.

sample

2
1 2
3 4

5