重生之我在原神做DP

时间限制：1s

空间限制：256MB

题目背景

你说的对，但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「提瓦特」的幻想世界，在这里，被神选中的人将被授予「神之眼」，导引元素之力。你将扮演一位名为$\lceil$旅行者$\rfloor$的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘$\lceil$原神$\rfloor$的真相。

近期原神开放了$4.3$版本，由于没有新的地图，$\lceil$旅行者$\rfloor$山里灵活的狗决定去肝一下须弥地图。然而须弥地图山高路远，道阻且长，山里灵活的狗苦不堪言，就想要借此出一道题，让大家一起痛苦一下。

题目描述

山里灵活的狗会给你一个 $n \times m$ 的地图 $heights$ ，其中 $heights[row][col]$ 表示位置 $(row, col)$ 处的高度。

一开始山里灵活的狗在最左上角 $(0, 0)$处 ，且希望去最右下角的$(n-1,m-1)$处 （注意下标从 $0$ 开始编号）。他每次可以往 上，下，左，右 四个方向之一移动，需要你找到耗费 体力 最小的一条路径。

一条路径所耗费的 体力 是指，路径上相邻位置之间 高度差绝对值 的 最大值 。

输入格式

第一行两个正整数$n,m$.表示地图$heights$的大小。

接下来$n$行，每行$m$个正整数，表示地图$heights$。

输出格式

一个非负整数，表示消耗的最小体力。

样例输入1

3 3
1 2 2
3 8 2
5 3 5

样例输出1

2

样例输入2

3 3
1 2 3
3 8 4
5 3 5

样例输出2

1

样例输入3

5 5
1 2 1 1 1
1 2 1 2 1
1 2 1 2 1
1 2 1 2 1
1 1 1 2 1

样例输出3

0

样例解释

样例一 路径为$[1,3,5,3,5]$.

样例二 路径为$[1,2,3,4,5]$.

样例三 每次走$1$的位置即可。

数据范围及约定

对于$20\%$的数据，$1 \le n,m\le 10$，且至少存在一条最优路径的长度$= n+m-1$.

对于$50\%$的数据，$1 \le n,m \le 10$.

对于$100\%$的数据，$1 \le n, m \le 300$.

对于所有数据，$1 \le heights_{i,j} \le 10^9$.