枠

画像の中から有益な情報を抽出する画像認識はコンピュータサイエンスの中でも重要な研究テーマのひとつです。デジタルカメラ、運転支援システム、防犯システムなどに幅広く応用されています。

このような研究のおかげで、私たちは画像解析を行うための多くのソフトウェアやプログラム集を使い様々な処理を行うことができます。一方、自力でプログラムを書いて解析することで、その仕組みを知り、楽しい時間を過ごすことができます。ここでは、一風変わった画像認識をしてみましょう。

画像として次のような各ピクセルが整数の値を持つ N × N のピクセルが入力として与えられます。この画像の中から、線の太さが１ピクセルの長方形の枠（わく）を１つ抽出します。

枠が覆うピクセルの値の和が最大となるような枠を抽出して、その和を報告するプログラムを作成して 下さい。ただし、下の図のように、縦、横のピクセル数が１つや２つの場合も枠とみなすものとします。

入力

入力は以下の形式で与えられる。

N
p1,1 p1,2 ... p1,N
p2,1 p2,2 ... p2,N
:
pN,1 pN,2 ... pN,N

１行目に縦と横のピクセル数 N (1 ≤ N ≤ 300) が与えられる。続く N 行に、i 行 j 列目のピクセルの値を表す整数 p_i,j (-1000 ≤ p_i,j ≤ 1000)が与えられる。

出力

ピクセル値の和が最大となるような枠の、ピクセル値の和を１行に出力する。

入出力例

入力例１

5
2 0 0 2 0
0 1 0 2 0
0 0 0 -1 0
0 4 0 3 0 
-1 0 0 1 0

出力例１

12

入力例２

3
0 0 0
0 -1 0
0 0 0

出力例２

0

---