Farmer John wants to take a picture of his grazing cows so he can hang it on his wall. The pasture is represented by a grid of N * N cells (like an NxN chessboard) (2≤N≤1000). The FD wants the cows to be distributed around the pasture with the following rules:
No two cows can be in the same cell.
Each sublattice of size 2×2 (total such sublattices are (N−1)×(N−1)) must contain exactly 2 cows
For example, this placement complies with the rules:
CCC
...
CCC
And such accommodation - no
C.C
.C.
C..
because the 2×2 region in the lower right contains only one cow.
There are no other restrictions. You can assume that the FD has an infinite number of cows.
Some cells are more preferable for PD than others. In particular, the FD considers. that if a cow is placed in a cell (i,j), the beauty of the photo is increased by a
ij (0≤a
ij≤1000) units.
Determine the maximum possible beauty of the correct placement of cows.
Input
The first line contains the number N. Each of the next N lines contains N integers. The j-th number in the i-th row from the top is the value a
ij.
Imprint
Print one integer - the maximum possible beauty of the resulting photo.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3
|
22 |
In this example, 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. |