4346: 「JOI 2017 Final」JOIOI 王国
内存限制：256 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**题目译自 [JOI 2017 Final](https://www.ioi-jp.org/joi/2016/2017-ho/) T3「 [JOIOI 王国](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho.pdf) / [The Kingdom of JOIOI](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-en.pdf)」**
> 为了兼顾表意清楚与简洁，我翻译时脑补了 $R_{\text{JOI}}$ 和 $R_{\text{IOI}}$，所以不要问我为啥原题找不到……
JOIOI 王国是一个 $H$ 行 $W$ 列的长方形网格，每个 $1\times 1$ 的子网格都是一个正方形的小**区块**。为了提高管理效率，我们决定把整个国家划分成两个省 JOI 和 IOI 。
我们定义，两个同省的区块**互相连接**，意为从一个区块出发，不用穿过任何一个不同省的区块，就可以移动到另一个区块。有公共边的区块间可以任意移动。
我们不希望划分得过于复杂，因此划分方案需满足以下条件：
* 区块不能被分割为两半，一半属 JOI 省，一半属 IOI 省。
* 每个省必须包含至少一个区块，每个区块也必须属于且只属于其中一个省。
* 同省的任意两个小区块互相连接。
* 对于每一行/列，如果我们将这一行/列单独取出，这一行/列里同省的任意两个区块互相连接。这一行/列内的所有区块可以全部属于一个省。
现给出所有区块的海拔，第 $i$ 行第 $j$ 列的区块的海拔为 $A_{i,j}$。设 JOI 省内各区块海拔的极差（最大值减去最小值） 为 $R_{\text{JOI}}$，IOI 省内各区块海拔的极差为 $R_{\text{IOI}}$。在划分后，省内的交流有望更加活跃。但如果两个区块的海拔差太大，两地间的交通会很不方便。 因此，理想的划分方案是 $\max(R_{\text{JOI}}, R_{\text{IOI}})$ 尽可能小。
你的任务是求出 $\max(R_{\text{JOI}}, R_{\text{IOI}})$ 至少为多大。
输入
第一行，两个整数 $H,W$，用空格分隔。
在接下来的 $H$ 行中，第 $i$ 行有 $W$ 个整数 $A_{i,1}, A_{i, 2}, \ldots, A_{i, W}$，用空格分隔。
输入的所有数的含义见题目描述。
输出
一行，一个整数，表示 $\max(R_{\text{JOI}}, R_{\text{IOI}})$ 可能的最小值。
样例输入 复制
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10样例输出 复制
11提示
输入样例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
数据范围：对于 $15\%$ 的数据，$H, W\leqslant 10$。 对于另外 $45\%$ 的数据，$H, W\leqslant 200$。 对于所有数据，$2\leqslant H, W\leqslant 2000, A_{i,j}\leqslant 10^9(1\leqslant i\leqslant H, 1\leqslant j\leqslant W)$。