#include <bits/stdc++.h>
using namespace std;
#define int long long
#define a3 array <int,4>
const int N=2005;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int INF=1e9+7;
int n,m,a[N][N],b[N][N];
bool vis[N][N],ck[N][N];
void bfs(int y,int x,int mid){
priority_queue <a3,vector <a3>,greater <a3>> pq;
pq.push({b[y][x],0,y,x});
while(!pq.empty()){
auto [b_u,mx_u,y,x]=pq.top();
pq.pop();
//cout << y << " " << x << "\n";
bool ok=true;
int cnt1=0,cnt2=0;
for(int i=0;i<4;i++){
int yy=y+dy[i],xx=x+dx[i];
if(yy<1 || yy>n || xx<1 || xx>m) continue;
if(vis[yy][xx]) cnt1++;
if(vis[yy][xx] && abs(a[y][x]-a[yy][xx])>mid) ok=false,cnt2++;
}
if(mx_u>mid || vis[y][x] || (!ok && cnt1==cnt2)) continue;
vis[y][x]=true;
//cout << "P";
for(int i=0;i<4;i++){
int yy=y+dy[i],xx=x+dx[i];
if(yy<1 || yy>n || xx<1 || xx>m || vis[yy][xx]) continue;
int mx=abs(a[y][x]-a[yy][xx]);
for(int j=0;j<4;j++){
int yyy=yy+dy[j],xxx=xx+dx[j];
//cout << "O";
if(yyy<1 || yyy>n || xxx<1 || xxx>m) continue;
if(vis[yyy][xxx] && ((b[yy][xx]==0) || (b[yy][xx]==1 && b[yyy][xxx]==1))) mx=max(mx,abs(a[yy][xx]-a[yyy][xxx]));
//cout << "P";
}
//cout << "O";
//cout << mx;
if(mx<=mid) pq.push({b[yy][xx],mx,yy,xx});
}
}
}
bool check(int mid){
memset(vis,false,sizeof(vis));
memset(ck,false,sizeof(ck));
bfs(1,1,mid);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ck[i][j]|=vis[i][j];
//cout << "OUT BFS1";
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<4;k++){
int ii=i+dy[k],jj=j+dx[k];
if(ii<1 || ii>n || jj<1 || jj>m) continue;
if(vis[i][j] && vis[ii][jj] && abs(a[i][j]-a[ii][jj])>mid) return false;
}
}
}
*/
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout << ck[i][j] << " ";
cout << "\n";
}
*/
int y=1,x=1,mx_d=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int mxx=0;
for(int k=0;k<4;k++){
int ii=i+dy[k],jj=j+dx[k];
if(ii<1 || ii>n || jj<1 || jj>m) continue;
mxx=max(mxx,abs(a[i][j]-a[ii][jj]));
}
if(!vis[i][j] && mxx>mx_d){
mx_d=mxx;
y=i,x=j;
}
}
}
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!vis[i][j]) b[i][j]=1;
//cout << y << " , " << x << "\n";
memset(vis,false,sizeof(vis));
bfs(y,x,mid);
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<4;k++){
int ii=i+dy[k],jj=j+dx[k];
if(ii<1 || ii>n || jj<1 || jj>m) continue;
if(vis[i][j] && vis[ii][jj] && abs(a[i][j]-a[ii][jj])>mid){
cout << i << " , " << j << " vs " << ii << " , " << jj << "\n";
return false;
}
}
}
}
*/
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout << vis[i][j] << " ";
cout << "\n";
}
*/
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ck[i][j]|=vis[i][j];
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!ck[i][j]) return false;
return true;
}
signed main()
{
//ios::sync_with_stdio(0);
//cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j];
int l=0,r=INF;
while(l<r){
int mid=(l+r)/2;
//cout << mid << "\n";
if(check(mid)) r=mid;
else l=mid+1;
}
cout << l;
//if(check(13)) cout << "OK";
//else cout << "SHIT";
//cout << "OK CK";
}
