北の牧草地で跳ねるレプラコーンを見た 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$ は行列の行 $i$ を構成する空白区切りの $N$ 整数です。

出力

• 行 1：上の規則で得られる最大の和を表す整数。

入出力例

入力 1

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

出力 1

24

問題出典：BOI'98 より改編, 2008