A Garden with Ponds (AOJ 1618, AOJ-ICPC 150 点) の制約強化版です。
問題文
H×W のマス目があります。以下、i 行目 j 列目 (1≤i≤H,1≤j≤W) のマス目をマス (i,j) と呼びます。
マス (i,j) には、整数 Aij が書かれています。
マス目のある部分長方形 {(i,j)∣1≤u≤i≤d≤H,1≤l≤j≤r≤W} は、以下の条件を満たすとき 良い 部分長方形であると呼びます。
- 大きさは縦・横ともに 3 以上である。つまり、d−u≥2,r−l≥2 が成り立つ。
- 長方形の外側に接するマスに書かれている値は、そうでないマスに書かれている値よりも大きい。つまり、(x1,y1),(x2,y2) をこの部分長方形内のマスとし、x1=u,x1=d,y1=l,y1=r のいずれかが成り立ち、かつ u<x2<d,l<y2<r が成り立つとき、Ax1y1>Ax2y2 である。
ある良い部分長方形 {(i,j)∣1≤u≤i≤d≤H,1≤l≤j≤r≤W} の容量 V を、以下のように定義します。
- h を、部分長方形内にあり i=u,i=d,j=l,j=r のいずれかが成り立つマス (i,j) についての Aij の最小値とする。
- V=h(d−u−1)(r−l−1)−∑i=u+1d−1∑j=l+1r−1Aij
良い部分長方形の容量の最大値を求めてください。ただし、良い部分長方形が存在しない場合、0 を出力してください。
制約
- 3≤H≤700
- 3≤W≤700
- 0≤Aij≤109(1≤i≤H,1≤j≤W)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
H W
A11 A12 ⋯ A1W
A21 A22 ⋯ A2W
⋮
AH1 AH2 ⋯ AHW
出力
良い部分長方形の容量の最大値を出力してください。ただし、良い部分長方形が存在しない場合、0 を出力してください。
サンプル
入力1
5 5
8 7 6 4 10
7 1 3 9 1
3 4 8 1 1
4 2 2 9 3
8 4 2 10 2
入力2
5 5
6 7 6 8 8
1 8 2 2 5
1 6 5 3 1
8 3 6 8 1
2 8 0 3 5