题目描述

有一个 $n\times n$ 的棋盘格，格子中分布着若干个奖励币，玩家总共可以做 $3$ 次操作，每次操作可以将一个格子中的奖励币放到相邻格子中（相邻格子指上下左右四个），最终全部操作做完后，可将其中一个格子中的奖励币拿走，问玩家能拿走的最大奖励币数量为多少？

输入格式

从文件 max.in 中读入数据。

总共 $n+1$ 行。

第一行一个正整数，表示棋盘格的行列数；

第 $2$ 行到第 $n+1$ 行每行 $n$ 个非负整数，表示每个格子具体奖励币的数量($数量＜10^{10}$)。

输出格式

输出到文件 max.out 中。

一个正整数，表示玩家最后能获得的最大奖励币数量。

样例 #1

样例输入 #1

2
1 2
3 4

样例输出 #1

10

样例 #2

样例输入 #2

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

样例输出 #2

58

提示

对于 $100\%$ 的数据，$1\le n\le10^3$。