AT_joi2017ho_c JOIOI 王国 (Kingdom of JOIOI)

[problemUrl]: https://atcoder.jp/contests/joi2017ho/tasks/joi2017ho_c

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

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

### 課題 JOIOI 王国の各マスの標高が与えられたとき，条件を満たすように地域の分割をした際の，地域 JOI の中での標高の最大値と最小値の差と，地域 IOI の中での標高の最大値と最小値の差のうち，大きい方の値の最小値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 2\ \leqq\ H\ \leqq\ 2\,000 $． - $ 2\ \leqq\ W\ \leqq\ 2\,000 $． - $ 1\ \leqq\ A_{i,\ j}\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ H $，$ 1\ \leqq\ j\ \leqq\ W $)． ### 小課題 1 \[15 点\] 以下の条件を満たす． - $ H\ \leqq\ 10 $． - $ W\ \leqq\ 10 $． ### 小課題 2 \[45 点\] 以下の条件を満たす． - $ H\ \leqq\ 200 $． - $ W\ \leqq\ 200 $． ### 小課題 3 \[40 点\] 追加の制限はない． - - - - - - ### Sample Explanation 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 J I J I I I ``` - - - - - -