题目描述

$Bob$ 最近喜欢爬山，他选择的爬山区域可以看作一个 $n \times m$ 网格，每个网格代表一座山的海拔高度。 $Bob$ 从 $(1,1)$ 出发向终点 $(n,m)$ 进发，每次他可以选择前、后、左、右、左前、左后、右前、右后 $8$ 个方向前进，但不能越界（走到网格外面）。

即从 (i,j) 出发，可以爬 (i+1,j),(i,j+1),(i-1,j),(i,j-1),(i+1,j+1),(i-1,j-1),(i+1,j-1),(i-1,j+1) 座山，但不能越界。

爬山的难度是一条路线上两座相邻山的海拔差的最大值，请帮助 $Bob$ 选择一条路线，从 $(1,1)$ 出发爬向 $(n,m)$，求爬山难度的最低值。

输入格式

第一行两个整数 $n$ 和 $m$ 。

接下来 $n$ 行，每行 $m$ 个整数，表示山的海拔高度 $h$ 。

输出格式

一个整数，表示爬山难度的最低值。

3 4
1 -2 3 4
3 5 4 -1
1 -5 2 0

2

2 3
1 1 1
1 1 1

0

2 2
100 100
100 -100

200

数据规模与约定

$Subtask1$ : $2\le n,m \le 100, 0 \le h \le 100$ , 数据随机构造，$50$ 分

$Subtask2$ : $2\le n,m \le 500, -10^9 \le h \le 10^9$ , $50$ 分