A close friend of yours, a duck with financial problems, has requested your help with a matter that will help him pay off his debts. He is the nephew of an extremely wealthy duck, who has a large vault, filled with mountains of coins. This wealthy duck has a certain coin in his possession which has a lot of sentimental value to him. Usually, it is kept under a protective glass dome on a velvet cushion.However, during a recent relocating of the coins in the vault, the special coin was accidentally moved into the vault, leading to an extremely stressful situation for your friend’s uncle. Luckily, the coin has recently been located. Unfortunately, it is completely opposite to the entrance to the vault, and due to the mountains of coins inside the vault, actually reaching the coin is no simple task.He is therefore willing to pay your friend to retrieve this coin, provided that he brings his own equipment to scale the mountains of coins. Your friend has decided he will bring a ladder, but he is still uncertain about its length. While a longer ladder means that he can scale higher cliffs, it also costs more money. He therefore wants to buy the shortest ladder such that he can reach the special coin, so that he has the largest amount of money left to pay off his debts.The vault can be represented as a rectangular grid of stacks of coins of various heights (in meters), with the entrance at the north west corner (the first height in the input, the entrance to the vault is at this height as well) and the special coin at the south east corner (the last height in the input). Your avian companion has figured out the height of the coins in each of these squares. From a stack of coins he can attempt to climb up or jump down to the stack immediately north, west, south or east of it. Because your friend cannot jump or fly (he is a very special kind of duck that even wears clothes), successfully performing a climb of nn meters will require him to bring a ladder of at least nn meters. He does not mind jumping down, no matter the height; he just lets gravity do all the work.

Input

The first line contains two integers: the length MM, and the width NN of the vault, satisfying 1 \leq M,N \leq 10001≤M,N≤1000.The following MM lines each contain NN integers. Each integer specifies the height of the pile of coins in the vault at the corresponding position. (The first line describes the north-most stacks from west to east; the last line describes the south-most stacks from west to east). The heights are given in meters and all heights are at least 00 and at most 10^9109 (yes, your friend’s uncle is very rich).

Output

Output a single line containing a single integer: the length in meters of the shortest ladder that allows you to get from the north west corner to the south east corner.

#### 样例输入1

3 3
1 2 3
6 5 4
7 8 9


#### 样例输出1

1


#### 样例输入2

1 4
4 3 2 1


#### 样例输出2

0


#### 样例输入3

7 5
10 11 12 13 14
11 20 16 17 16
12 10 18 21 24
14 10 14 14 22
16 18 20 20 25
25 24 22 10 25
26 27 28 21 25


#### 样例输出3

3


### 想法

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0)
using namespace std;
struct node{
int x,y,v;
bool operator<(const node & o)const{ //v代表每一个点到起点需要的梯子数量
return v>o.v;
}
};
priority_queue<node> p;
bool vis[1006][1006];
int arr[1006][1006],dir[4][2]={1,0,-1,0,0,1,0,-1},n,m;
int bfs(){
int num=0;
while(!p.empty()){
node d=p.top();
p.pop();
int x=d.x,y=d.y,v=d.v;
if(x==n&&y==m) return v; //到达了终点
if(vis[x][y]) continue;
vis[x][y]=1; //记得标记
for(int i=0;i<4;++i){
int x1=x+dir[i][0],y1=y+dir[i][1];
if(x1<=0||x1>n||y1<=0||y1>m) continue;
int tmp;
if(arr[x1][y1]-arr[x][y]<0) tmp=0; //这是刚开始如果下一个点比这个点小不能用负数，得用0
else tmp=arr[x1][y1]-arr[x][y]; 这段需要的梯子长度
int v1=max(v,tmp); //取他们较大的那个
p.push({x1,y1,v1}); //放进队列
}
}
}
int main()
{
ios;
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>arr[i][j];
}
}
p.push({1,1,0});
cout<<bfs()<<'\n';
}