该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在各路好汉的帮助下，解药及时送达，武大郎转危为安！武大郎感动涕零，武松也对张昊老师的智谋佩服得五体投地。得知张昊老师来自未来后，武松拿出了早年在景阳冈一处古洞府寻得的“破空阵盘”，希望能助恩人返乡。 阵盘是一个 $N \times N$ 的网格，要在其中嵌入充满灵力的符石才能激活时空裂隙。但阵法极为讲究阴阳平衡：任何一个 $2 \times 2$ 的局部区域内，必须恰好镶嵌 2 颗符石，否则阵法会瞬间崩溃。张昊老师发现，每个网格位置能激发的灵力值不同。为了确保穿越的能量充足且平稳，他必须找到一种符石的排布方案，使得总灵力值最大化。

题目描述

破空阵盘可以看作是一个 $N \times N$ 的网格（$2 \le N \le 1000$）。张昊老师需要在网格中放置符石。为了保持阵法稳定，必须严格遵守以下规则：同一个网格单元内最多只能放置 1 颗符石。对于每一个 $2 \times 2$ 的子网格（总共有 $(N-1) \times (N-1)$ 个这样的子网格），必须恰好包含 2 颗符石。例如，以下的排布是合法的（C代表符石，.代表空）：

CCC
...
CCC

而以下的排布是不合法的，因为右下角的 $2 \times 2$ 区域内只有 1 颗符石：

C.C
.C.
C..

你可以假设张昊老师拥有无数颗符石。每个网格单元 $(i, j)$ 都有一个潜在的灵力值 $a_{i,j}$（$0 \le a_{i,j} \le 1000$）。如果在该单元格放置一颗符石，阵法的总灵力就会增加 $a_{i,j}$。请帮助张昊老师确定，在满足所有规则的前提下，阵法能够达到的最大总灵力值是多少？

输入格式

第一行包含一个整数 $N$。 接下来的 $N$ 行，每行包含 $N$ 个整数。 第 $i$ 行的第 $j$ 个整数代表 $a_{i,j}$。

输出格式

输出一个整数，表示合法排布下的最大总灵力值。

样例输入

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$。

数据范围：

测试点 2-4 满足 $N \le 4$。 测试点 5-10 满足 $N \le 10$。 测试点 11-20 满足 $N \le 1000$。