该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

是一个 $R \times C$ 的网格地图，每个格点 $(i, j)$ 都有一个辐射值 $H_{i,j}$。 你需要驾驶一辆特殊的防护车从左上角 $(1, 1)$ 移动到右下角 $(R, C)$。车辆只能向上下左右四个相邻格子移动。 车辆有一个“抗辐射剧变能力” $X$。如果从格子 $A$ 移动到相邻格子 $B$，要求两个格子的辐射值差的绝对值不能超过 $X$，即 $|H_A - H_B| \le X$。 请问，为了能从起点到达终点，车辆的最小抗辐射剧变能力 $X$ 应该是多少？

输入格式

第一行两个整数 $R, C$ ($1 \le R, C \le 500$)。 接下来 $R$ 行，每行 $C$ 个整数，表示网格的辐射值 $H_{i,j}$ ($0 \le H_{i,j} \le 10^9$)。

输出格式

输出一个整数，表示最小的 $X$。

样例输入

3 3
1 3 5
2 8 6
4 5 9

样例输出

3