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)$ 中放有一头奶牛，照片的美丽度会增加 $a_{ij}$ 单位。

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

输入格式

输入的第一行包含 $N$。

以下 $N$ 行每行包含 $N$ 个整数。从上到下第 $i$ 行的第 $j$ 个整数为 $a_{ij}$ 的值。

输出格式

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

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

22

提示

$2≤N≤1000$, $0≤a_{ij}≤1000$

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

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

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