2334 [JOI 2016/2017 本選] JOIOI 王国

JOIOI 王国は $H$ 行 $W$ 列のマスに区切られた長方形の形をしている．JOIOI 王国では，行政の効率化のため，国全体を2 つの地域 JOI とIOI に分けることにした．

地域の分け方が複雑になりすぎるのを防ぐため，以下の条件を満たすように分割を行うことにした：

• 各地域は，1 つ以上のマスを含む．
• それぞれのマスは，2 つの地域のうちのちょうど1 つに属する．
• 地域 JOI に属するどの 2 つのマスの間も，その地域に属さないマスに入らずに辺で接しているマスへの移動を繰り返すことにより移動できる．地域 IOI についても同様である．
• 各行，各列について，その行または列に属するマス全体を取り出したとき，それぞれの地域のマスはひとつながりになっている．ただし，その行あるいは列のすべてのマスが同じ地域に属していてもよい．

各マスには標高と呼ばれる整数が定まっている．地域への分割を行った後は，各地域内での移動が活発になると想定される．地域内での標高の差があまりに大きいと移動が大変であるため，同じ地域内での標高差ができるだけ小さくなるように分割を行いたい．すなわち，地域JOI の中での標高の最大値と最小値の差と，地域IOI の中での標高の最大値と最小値の差のうち，大きい方の値を最小化したい．

JOIOI 王国の各マスの標高が与えられたとき，条件を満たすように地域の分割をした際の，地域JOI の中での標高の最大値と最小値の差と，地域 IOI の中での標高の最大値と最小値の差のうち，大きい方の値の最小値を求めるプログラムを作成せよ．

標準入力から以下の入力を読み込め．

• 1 行目には，2 個の整数 $H, W$ が空白を区切りとして書かれている．これらは，JOIOI 国が $H$ 行 $W$ 列のマスに区切られた長方形の形をしていることを表す．
• 続く $H$ 行のうちの $i$ 行目($1 \leq i \leq H$) には，$W$ 個の整数 $A_{i,1},$ $A_{i,2},$ $\ldots,$ $A_{i,W}$ が空白を区切りとして書かれている．これは，JOIOI 王国の上から $i$ 行目，左から $j$ 列目($1 \leq j \leq W$) の標高が $A_{i, j}$ であることを表す．

標準出力に，条件を満たすように地域の分割をした際の，地域 JOI の中での標高の最大値と最小値の差と，地域 IOI の中での標高の最大値と最小値の差のうち，大きい方の値の最小値を 1 行で出力せよ．

この入力例では，例えば下の図のように地域を分割すればよい．ここで，J は地域 JOI，I は地域 IOI を表す．

J J J I
J J J I
J J I I
J I I I

ここで，例えば次のような分割は，左から3 列目において地域 IOI がひとつながりになっていないため，条件を満たす分割ではない．

J J I I
J J J I
J J I I
J I I I

すべての入力データは以下の条件を満たす．

• $2 \leq H \leq 2 000$．
• $2 \leq W \leq 2 000$．
• 1$ \leq A_{i, j} \leq 10^9$ $(1 \leq i \leq H,$ $1 \leq j \leq W)$．

小課題1 [15点] $\quad$ $H,W≤10$ を満たす．
小課題2 [45点] $\quad$ $H,W≤200$ を満たす．
小課題3 [40点] $\quad$ 追加の制限はない．