JOIOI 王国は $H$ 行 $W$ 列のマスに区切られた長方形の形をしている.JOIOI 王国では,行政の効率化のため,国全体を2 つの地域JOI とIOI に分けることにした.
地域の分け方が複雑になりすぎるのを防ぐため,以下の条件を満たすように分割を行うことにした:
各マスには標高と呼ばれる整数が定まっている.地域への分割を行った後は,各地域内での移動が活発になると想定される.地域内での標高の差があまりに大きいと移動が大変であるため,同じ地域内での標高差ができるだけ小さくなるように分割を行いたい.すなわち,地域JOI の中での標高の最大値と最小値の差と,地域IOI の中での標高の最大値と最小値の差のうち,大きい方の値を最小化したい.
JOIOI 王国の各マスの標高が与えられたとき,条件を満たすように地域の分割をした際の,地域JOI の中での標高の最大値と最小値の差と,地域IOI の中での標高の最大値と最小値の差のうち,大きい方の値の最小値を求めるプログラムを作成せよ.
標準入力から以下の入力を読み込め.
標準出力に,条件を満たすように地域の分割をした際の,地域JOI の中での標高の最大値と最小値の差と,地域IOI の中での標高の最大値と最小値の差のうち,大きい方の値の最小値を1 行で出力せよ.
すべての入力データは以下の条件を満たす.
4 4 1 12 6 11 11 10 2 14 10 1 9 20 4 17 19 10
11
この入力例では,例えば下の図のように地域を分割すればよい.ここで,J は地域JOI,I は地域IOI を表す.
ここで,例えば次のような分割は,左から3 列目において地域IOI がひとつながりになっていないため,条件を満たす分割ではない.
8 6 23 23 10 11 16 21 15 26 19 28 19 20 25 26 28 16 15 11 11 8 19 11 15 24 14 19 15 14 24 11 10 8 11 7 6 14 23 5 19 23 17 17 18 11 21 14 20 16
18