4222. Chtholly Nota Seniorious

【题目背景】

こんなにも、たくさんの幸せをあの人に分けてもらった

だから、きっと

今の、私は

谁が何と言おうと

##世界一、幸せな女の子だ

【题目描述】

——“假如……我是说假如喔。

万一我再过五天就会死，你能不能对我温柔一点？”

巨大的六号兽五天后将袭击浮游大陆。

无数次计算得到的残酷数据表明，只有圣剑瑟尼欧尼斯的适格精灵——珂朵莉·诺塔·瑟尼欧尼斯（Chtholly Nota Seniorious）开启妖精乡之门，才可以以生命为代价守住浮游岛。

“至少，我也希望自己不用消失，也想让别人记住。我也想留下羁绊啊。”

留给妖精少女珂朵莉的时间似乎已经不多了。

年轻的二等技官，妖精仓库的管理员，世界上最后一个人类——威廉·克梅修，数百年前曾经是一名准勇者，掌握着成为一名勇者所需要的所有知识。

大战在即，调整圣剑的状态成为了一项重要的任务。

瑟尼欧里斯（セニオリス）
圣剑的其中之一，在现存的遗迹兵装中，拥有最强大的力量。
拥有非常特殊的资质，只有极少一部分的人才能使用。
由四十一个护符组成。能将所有事物包含不死者都回归「死亡」。

威廉需要调整圣剑的状态，因此他将瑟尼欧尼斯拆分护符，组成了一个 $n$ 行 $m$ 列的矩阵。

每一个护符都有自己的魔力值。现在为了测试圣剑，你需要将这些护符分成 $A,B$ 两部分。

要求如下：

1. 圣剑的所有护符，恰好都属于两部分中的一部分。
   
2. 每个部分内部的方块之间，可以通过上下左右相互到达，而且每个内部的方块之间互相到达，最多允许拐一次弯。

例如

AAAAA  AAAAA  AAAAA
AABAA  BaAAA  AAABB
ABBBB  BBAAA  AAABB
AABAA  BaAAA  ABBBB
AAAAA  AAAAA  BBBBB

 (1)    (2)    (3)

其中(1)(2)是不允许的分法，(3)是允许的分法。在(2)中，a 属于 A 区域，这两个 a 元素之间互相到达，没有办法最多只拐一次弯。

现在要问，所有合法的分法中，A 区域的极差与 B 区域的极差 中间较大的一个的 最小值 是多少？

好心而可爱的在一旁默默观察奈芙莲悄悄地告诉你，极差就是区域内最大值减去最小值。

夜晚的风吹拂着，68 号岛上的景色竟与地上的森林无异。转念又想，黄金妖精本身就是与森林之中出现，成长，消亡的神秘存在啊。

时间不早了，早上训练中落败的珂朵莉即将回来了。您要尽快和威廉一起调整好圣剑，千万不能迟哟。

【输入格式】

第一行两个自然数 $n,m$

接下来 $n$ 行，每行 $m$ 个自然数 $A_{i,j}$ 表示权值

【输出格式】

一个整数表示答案。

【样例输入】

4 4
1 12 6 11
11 4 2 14
10 1 9 20
4 17 13 10

【样例输出】

11

【样例说明】

1  12 6        11
11 4  2        14
10 1  9        20
4        17 13 10

分法不唯一，如图是一种合法的分法。左边部分极差 $12-1=11$，右边一块极差 $20-10=10$，所以答案取这两个中较大者 $11$。没有别的分法，可以使答案更小。

【数据规模与约定】

对于所有的权值 $1 \le A_{i,j} \le 10^9$

《末日时在做什么？有没有空？可以来拯救吗？》

【来源】

洛谷 P3933