#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define nl << '\n'
#define sp << ' ' <<
int h, w;
int g[2000][2000], a[2000], maxElement, minElement;
bool possible(int diff){
int res = 0;
for(int i=0; i<h; ++i){
a[i] = 0;
for(int j=0; j<w; ++j){
if(g[i][j]-minElement<=diff and a[i]==j) ++a[i];
else res = max(res, maxElement-g[i][j]);
}
}
return res<=diff;
}
int search(){
int res = maxElement - minElement;
int low = 0, high = res;
while(low<high){
int mid = (low+high)/2;
if(possible(mid)) high = mid;
else low = mid+1;
}
return low;
}
void rotate(){
int g0[h][w];
for(int i=0; i<h; ++i)
for(int j=0; j<w; ++j)
g0[i][j] = g[i][j];
swap(h, w);
for(int i=0; i<h; ++i)
for(int j=0; j<w; ++j)
g[i][j] = g0[j][w-1-i];
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> h >> w;
for(int i=0; i<h; ++i)
for(int j=0; j<w; ++j)
cin >> g[i][j];
int ans = 2e9;
maxElement = minElement = g[0][0];
for(int i=0; i<h; ++i)
for(int j=0; j<w; ++j)
maxElement = max(maxElement, g[i][j]), minElement = min(minElement, g[i][j]);
for(int _=0; _<4; ++_){
if(_) rotate();
ans = min(ans, search());
}
cout << ans;
}
