#include <bits/stdc++.h>
//#define int long long
//#define double long double
#define Nanase_Kurumi_aka_menhera_chan_is_mine ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define pi pair<double,int>
#define ALL(i) i.begin(),i.end()
#define gcd(i,j) __gcd(i,j)
#define fi first
#define se second
#define eps 0.00000001
#define ist insert
#define DNE nullptr
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
//#pragma GCC optimize("O2")
int max(int x,int y){return x>=y?x:y;}
int min(int x,int y){return x>=y?y:x;}
using namespace std;
typedef int ll;
const int N=2005;
const int M=1000005;
const int MOD=1000000007;//998244353;
const int INF=2147483647;//1000000000000000000;
int n,m,ans;
int a[N][N];
int premx[N][N],sufmx[N][N],premn[N][N],sufmn[N][N];
vector<int> vc,res;
int calc(){
int mx=0,mn=INF,sum=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=vc[i];j++)
mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);
/*mx=max(mx,premx[i][vc[i]]);
mn=min(mn,premn[i][vc[i]]);*/
}
sum+=mx-mn;
mx=0;mn=INF;
for (int i=1;i<=n;i++){
for (int j=vc[i]+1;j<=m;j++)
mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);
/*mx=max(mx,sufmx[i][vc[i]+1]);
mn=min(mn,sufmn[i][vc[i]+1]);*/
}
//sum+=mx-mn;
return max(sum,mx-mn);
}
int _calc(vector<int> &t){
int mx=0,mn=INF,sum=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=t[i];j++)
mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);
/*mx=max(mx,premx[i][t[i]]);
mn=min(mn,premn[i][t[i]]);*/
}
sum+=mx-mn;
mx=0;mn=INF;
for (int i=1;i<=n;i++){
for (int j=t[i]+1;j<=m;j++)
mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);
/*mx=max(mx,sufmx[i][t[i]+1]);
mn=min(mn,sufmn[i][t[i]+1]);*/
}
//sum+=mx-mn;
return max(sum,mx-mn);
}
void dfs(int i){
if (i==n){
ans=min(ans,calc());
vector<int> t(ALL(vc));t.pb(0);
reverse(ALL(t));
ans=min(ans,_calc(t));
return;
}
for (int k=vc.back();k<=m;k++){
vc.pb(k);
dfs(i+1);
vc.pop_back();
}
}
inline void sol(){
cin >>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
cin >>a[i][j];
/*for (int i=1;i<=n;i++){
fill(premn[i],premn[i]+m+1,INF);
fill(sufmn[i],sufmn[i]+m+1,INF);
for (int j=1;j<=m;j++){
premx[i][j]=max(a[i][j],premx[i][j-1]);
premn[i][j]=min(a[i][j],premn[i][j-1]);
}
for (int j=m;j>=1;j--){
sufmx[i][j]=max(a[i][j],sufmx[i][j+1]);
sufmn[i][j]=min(a[i][j],sufmn[i][j+1]);
}
}*/
ans=INF;
vc.pb(0);
for (int i=0;i<=m;i++){
vc.pb(i);
dfs(1);
vc.pop_back();
}
cout <<ans<<'\n';
//for (int &i:res) cout <<i<<' ';
}
signed main(){
Nanase_Kurumi_aka_menhera_chan_is_mine
int _=1;
//cin >>_;
while (_--) sol();
return 0;
}
