8107: Spaced Out

Farmer John 想要拍摄一张他的奶牛吃草的照片挂在墙上。

草地可以用一个 N 行 N 列正方形方格所组成的方阵表示（想象一个 N×N 的棋盘）。

在 Farmer John 最近拍摄的照片中，他的奶牛们太过集中于草地上的某个区域。

这一次，他想要确保他的奶牛们分散在整个草地上。

于是他坚持如下的规则：

没有两头奶牛可以位于同一个方格。

所有 2×2 的子矩阵（共有 (N−1)×(N−1) 个）必须包含恰好 2 头奶牛。

例如，这一放置方式是合法的：

CCC

...

CCC

而这一放置方式是不合法的，因为右下的 2×2 正方形区域仅包含 1 头奶牛：

C.C

.C.

C..

没有其他限制。

你可以假设 Farmer John 有无限多的奶牛（根据以往的经验，这种假设似乎是正确的……）。

Farmer John 更希望某些方格中包含奶牛。

具体地说，他相信如果方格 (i,j) 中放有一头奶牛，照片的美丽度会增加 aij 单位。

求合法的奶牛放置方式的最大总美丽度。

输入格式

输入的第一行包含 N。

以下 N 行每行包含 N 个整数。从上到下第 i 行的第 j 个整数为 aij 的值。

输出格式

输出一个整数，为得到的照片的最大美丽度。

数据范围

2≤N≤1000,

0≤aij≤1000

输入样例：

4

3 3 1 1

1 1 3 1

3 3 1 1

1 1 3 3

输出样例：

22

样例解释

在这个样例中，最大美丽度可以在如下放置方式时达到：

CC..

..CC

CC..

..CC

这种放置方式的美丽度为 3+3+3+1+3+3+3+3=22。


Farmer John wants to take a picture of his cows grazing in their pasture to hang on his wall. The pasture is represented by an N by N grid of square cells (picture an N×N chess board), with 2≤N≤1000. In the last picture Farmer John took, his cows were too clumped together in one region of the pasture. This time around, he wants to make sure his cows are properly spaced out across the pasture. He therefore insists on the following rules:

• No two cows may be placed in the same cell.
• Every sub-grid of 2×2 cells ((N−1)×(N−1) of them in total) must contain exactly 2 cows.

For example, this placement is valid:

CCC
...
CCC

while this placement is not, because the 2×2 square region that contains the bottom-right corner cell contains only 1 cow:

C.C
.C.
C..

There are no other restrictions. You may assume that Farmer John has an infinite number of cows available (based on previous experience, this assumption certainly seems to be true...).

Farmer John wants some cells to contain cows more than other cells. In particular, he believes that when a cow is placed in cell (i,j), the beauty of the picture is increased by aij (0≤aij≤1000) units.

Determine the maximum possible total beauty of a valid placement of cows.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

22

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=223+3+3+1+3+3+3+3=22.