Distributed#11200

Distributed

1 second

128 megabytes

Hard

Farmer John wants to take a photo of his grazing cows and hang it on the wall. The pasture is represented by a grid of size $n \times n$ n \times n cells (like a chessboard of size $n \times n$ n \times n). Farmer John wants to place cows on the pasture according to the following rules:

No two cows can be in the same cell.
Each $2 \times 2$ 2 \times 2 subgrid (there are $(n - 1) \times (n - 1)$ (n - 1) \times (n - 1) such subgrids in total) must contain exactly $2$ cows.

For example, this placement follows the rules:

CCC
...
CCC

But this placement does not:

C.C
.C.
C..

because the $2 \times 2$ 2 \times 2 region in the bottom right corner contains only one cow.

There are no other restrictions. You can assume that Farmer John has an infinite number of cows.

Some cells are more preferable to Farmer John than others. Specifically, he believes that if a cow is placed in cell $(i, j)$ , the beauty of the photo increases by $a_{ij}$ a_{ij} ( $0 \leq a_{ij} \leq 1000$ 0 \le a_{ij} \le 1000) units.

Determine the maximum possible beauty of a valid cow placement.

Input

The first line contains the number $n$ ( $2 \leq n \leq 1000$ 2 \le n \le 1000). Each of the next $n$ lines contains $n$ integers. The $j$ -th number in the $i$ -th line from the top is the value $a_{ij}$ a_{ij}.

Output

Output a single integer - the maximum possible beauty of the resulting photo.

Examples

Example 1

Note

In this example, 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$ 3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22.