A Garden with Ponds (Hard)

2 secs 1024 MB
SSRS

A Garden with Ponds (AOJ 1618, AOJ-ICPC 150 点) の制約強化版です。

問題文


のマス目があります。以下、 行目 列目 のマス目をマス と呼びます。

マス には、整数 が書かれています。

マス目のある部分長方形 は、以下の条件を満たすとき 良い 部分長方形であると呼びます。

  • 大きさは縦・横ともに 以上である。つまり、 が成り立つ。
  • 長方形の外側に接するマスに書かれている値は、そうでないマスに書かれている値よりも大きい。つまり、 をこの部分長方形内のマスとし、 のいずれかが成り立ち、かつ が成り立つとき、 である。

ある良い部分長方形 の容量 を、以下のように定義します。

  • を、部分長方形内にあり のいずれかが成り立つマス についての の最小値とする。

良い部分長方形の容量の最大値を求めてください。ただし、良い部分長方形が存在しない場合、 を出力してください。

制約


  • 入力はすべて整数

入力


入力は以下の形式で標準入力から与えられます。

出力


良い部分長方形の容量の最大値を出力してください。ただし、良い部分長方形が存在しない場合、 を出力してください。

サンプル


入力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
出力1
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
出力2
0

Submit


Go (1.14)