[Usaco2009 Feb]The Leprechaun 寻宝

贝茜在牧场上发现了一只妖精，并迅速抓住了他。妖精答应满足她一个愿望，贝茜选择了获得财富的机会。

妖精在地上画出一个 $N\times N$ 的方格，并在每个格子中写下一个介于 $-10^6$ 和 $10^6$ 之间的整数。贝茜可以选择沿水平方向、竖直方向或对角线方向行走，每一步移动到该方向上相邻的格子。她经过的所有格子中的数字之和，就是她获得的财富。

这个方格具有首尾相接的特性：从一行的边界继续前进，会从该行的另一端出现；列和对角线方向也是如此。因此，每一行、每一列以及每一条对角线都可以视为循环相连。

请在某一行、某一列或某一条对角线上选择一段连续的数字，使它们的和最大，并求出这个最大值。

输入格式

第一行输入一个整数 $N$。

接下来 $N$ 行，每行包含 $N$ 个整数，表示方格中的数字。

输出格式

输出一个整数，表示能够获得的最大数字和。

样例输入

4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2

样例输出

24

数据范围

• $1\le N\le 200$；
• 方格中每个整数的取值范围为 $[-10^6,10^6]$。

来源与许可

本题为 USACO 2009 年 $2$ 月试题「The Leprechaun」，题面与测试数据整理自 BZOJ 1723。

样例 1

输入

4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2

输出

24