配点: 100 点
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 \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 以行的形式输出。
制限
所有输入数据满足以下条件。
- 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 点]
没有其他限制。
入力例 1
4 4 1 12 6 11 11 10 2 14 10 1 9 20 4 17 19 10
出力例 1
11
在此输入示例中,您可以如下图所示划分区域。其中,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
入力例 2
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
出力例 2
18