#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=2005;
int a[nmax][nmax];
int mn,mx,ans,n,m,i,j;
int st,dr,l,r;
bool cresc,desc;
bool check(int val)
{
st=0,dr=m;
cresc=1,desc=1;
for(i=1;i<=n&&(cresc||desc);i++)
{
r=1;l=m;
while(a[i][r]-mn<=val&&r<=m)
r++;
r--;
while(mx-a[i][l]<=val&&l>0)
l--;
st=max(st,l);dr=min(r,dr);
if(st>r)
cresc=0;
if(dr<l)
desc=0;
}
return (cresc||desc);
}
int solve()
{
int ret=(1<<30)-1;
for(int p=29;p>=0;p--)
if(check(ret-(1<<p)))
ret-=(1<<p);
return ret;
}
int main()
{
// freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>m;mn=(1<<30);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>a[i][j];
mn=min(a[i][j],mn);
mx=max(a[i][j],mx);
}
ans=mx-mn;
ans=min(solve(),ans);
for(i=1;i<=n;i++)
for(j=1;j<=m/2;j++)
swap(a[i][j],a[i][m-j+1]);
ans=min(solve(),ans);
cout<<ans;
return 0;
}
