想像 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