BH大逃亡

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

继上次 BH 选美的故事 (Bai Hao Wanna Have A Girl Friend) 之后,BH 如愿以偿地找到了女朋友。然而,羡慕嫉妒恨且又被 BH 恶搞过的 Stone 决定开始追杀 BH。

BH 要找一个安全的地方来躲避 Stone 的追杀,现在他有一张地图,地图上标注好了每一个地方的海拔(包括低于海平面的地方)。

另一边,Stone 为了抓到 BH,特地向最近成功进化到究极体的金桔 (QAQ) 学了一个技能,这个技能使他能以自身的位置 (i, j) 为左上角,(i+1, j+2) 为右下角,形成一个 2 行 3 列的膜法阵(膜法阵的尺寸必须为 2 行 3 列且不能超出地图边界,否则将不能形成膜法阵)。BH 只能在 Stone 的膜法阵范围内活动。

BH 本着能躲一秒是一秒的原则,试图跑到和 Stone 海拔相差最大的地方。现在,他想知道在所有可能的情况中,他们俩的海拔差最大可能是多少 ,如果你能告诉他,BH 会感谢你并拿出库存的 Accepted 标记送给你。

Input

输入数据有多组(数据组数不超过 20),到 EOF 结束。

每组先输入 n 和 m (3 <= n, m < 100),表示地图大小。
接下来有 n 行,每行 m 个数表示每一个地方的海拔 hi (-10000 < hi < 10000)。

Output

对于每组输入,输出一个数表示 BH 和 Stone 最大的海拔差。

Sample Input

3 3
1 2 3
1 2 3
1 2 3

Sample Output

2

Hint

对于示例数据,Stone 可以释放膜法阵的位置有 (0, 0) 和 (1, 0)。

以 (0, 0) 为例,此时 BH 只能在 (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1,2) 这六个位置活动。

Source

【2016级ACM集训队第一次选拔赛】Q^Q (cyk)