Frame

Time Limit : 1 sec, Memory Limit : 65536 KB

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

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

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


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


入力

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

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

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

出力

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

入出力例


入力例1

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

出力例1

12

入力例2

3
0 0 0
0 -1 0
0 0 0

出力例2

0

Source: PC Koshien 2014 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2014-11-8
http://web-ext.u-aizu.ac.jp/pc-concours/