想象 Bessie 在北边牧场看到一只矮妖蹦跳而过时有多惊讶。她可不是傻瓜，冲上前去，用能抓握的蹄子捉住了他。
“一个愿望，牛儿。我能给奶牛的只有这么多。”他说。
“财富，”Bessie 梦幻地说，“获得财富的机会。”
矮妖从不以最容易的方式实现捕捉者的愿望。一声巨响后，烟雾散去，一个闪闪发光的甜甜圈在青翠田野上缓缓旋转。
“我给你造了一个环面，”矮妖轻声说，“上面有一个 $N\times N$ 的矩阵 $(1 \le N \le 200)$，整数在 $-1{,}000{,}000,\ldots,1{,}000{,}000$ 范围内，决定你财富的多少。你必须在环面所有可能序列中，找出同一行、同一列或同一对角线上的连续整数序列，使和最大。”
Bessie 想了想，明白环面会把矩阵的列、行和对角线“卷绕”起来，因此可以选取跨过侧边或顶边后回绕的连续元素。
Bessie 会把矩阵告诉你。确定最大可能和（必须至少选择一个矩阵元素）。
例如，看下面左侧的 $4\times4$ 矩阵，其中标记了一条示范性的回绕对角线的全部元素：
8 6 6* 1 8 6* 6 1
-3 4 0 5* -3 4 0 5
4* 2 1 9 4 2 1 9*
1 -9* 9 -2 1 -9 9*-2右侧矩阵标记的对角线含两个 9（可用的最大数）和一个 6，和为 24。这是此矩阵的最大可能和，只取了该对角线四个可选元素中的三个。
输入格式
- 第 1 行：一个整数 $N$。
- 第 $2,\ldots,N+1$ 行：第 $i+1$ 行包含 $N$ 个空格分隔的整数，构成矩阵第 $i$ 行。
输出格式
- 第 1 行：一个整数，表示按上述规则能得到的最大和。
样例
输入格式 1
4 8 6 6 1 -3 4 0 5 4 2 1 9 1 -9 9 -2
输出格式 1
24
题目来源：改编自 BOI'98，2008