#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
const int H=2005,W=2005;
int h,w,lo,hi;
int g[H][W];
bool check(int x){
int losen=w+1;
for(int i=1; i<=h; i++){
int lopo=0;
for(int j=1; j<=w; j++){
if(lo+x < g[i][j]) break;
lopo++;
}
losen=min(losen,lopo);
int hipo=w+1;
for(int j=w; j>=1; j--){
if(hi-x > g[i][j]) break;
hipo--;
}
if(losen + 1 < hipo) return 0;
}
return 1;
}
void flip_row(){
for(int i=1; i<=h; i++){
for(int j=1; j<=w/2; j++){
swap(g[i][j],g[i][w-j+1]);
}
}
}
void flip_col(){
for(int j=1; j<=w; j++){
for(int i=1; i<=h/2; i++){
swap(g[i][j],g[h-i+1][j]);
}
}
}
bool f(int x){
bool an=0;
if(check(x)) an=1;
flip_row();
if(check(x)) an=1;
flip_col();
if(check(x)) an=1;
flip_row();
if(check(x)) an=1;
flip_col();
return an;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>h>>w;
lo=1e9+500; hi=-1e6;
for(int j=0; j<=w+1; j++) g[0][j]=0;
for(int i=1; i<=h; i++){
g[i][0]=0;
for(int j=1; j<=w; j++){
cin>>g[i][j];
lo=min(lo,g[i][j]);
hi=max(hi,g[i][j]);
}
g[i][w+1]=0;
}
for(int j=0; j<=w+1; j++) g[h+1][j]=0;
int l=0, r=1e9+100;
while(l<r){
int m=l+((r-l)/2);
if(f(m)) r=m;
else l=m+1;
}
cout<<l;
//checkc(5);
}
