题目描述

小 A 在一个 $N \times M$ 的网格中行走，起点在左上角 $(1,1)$，终点在右下角 $(N,M)$。每个格子 $(i,j)$ 有一个整数海拔值 $H_{i,j}$。

小 A 每步只能向右或向下移动一格。他希望所走路径上最大海拔与最小海拔之差尽可能小（即路径尽量平稳）。

请计算从起点到终点所有路径中，$(\text{路径最大海拔} - \text{路径最小海拔})$ 的最小值。

输入格式

第一行两个正整数 $N$、$M$。

接下来 $N$ 行，每行 $M$ 个整数，表示 $H_{i,j}$。

输出格式

输出一个整数，表示最小海拔差值。

输入示例 1

3 3
1 3 5
3 2 6
4 7 8

输出示例 1

7

示例说明

所有路径均经过起点 $(1,1)=1$ 和终点 $(3,3)=8$，差值至少为 $8-1=7$，故答案为 $7$。

输入示例 2

1 1
5

输出示例 2

0

示例说明

只有一个格子，路径上只有一个值，差值为 $0$。

数据范围

对于全部数据：$1 \le N, M \le 100$，$0 \le H_{i,j} \le 200$。