#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = int;
const ll INF = 1e9+1;
int value(pair<int, int> x) {
return max(x.st, x.nd);
}
ll solve(vector<vector<ll>>& grid) {
int h = grid.size(), w = grid[0].size();
ll L = INF, R = 0;
for(int i=0; i<h; ++i) {
for(int j=0; j<w; ++j) {
L = min(L, grid[i][j]);
R = max(R, grid[i][j]);
}
}
vector<vector<pair<int, int>>> dp(h+1, vector<pair<int, int>>(w+1));
for(int i=1; i<=h; ++i) {
int mx = L;
dp[i][0] = dp[i-1][0];
for(int j=1; j<=w; ++j) {
mx = max(mx, grid[i-1][j-1]);
dp[i][j] = dp[i-1][j];
if(value(dp[i][j-1]) < value(dp[i][j])) {
dp[i][j] = dp[i][j-1];
}
dp[i][j].st = max(dp[i][j].st, mx-L);
}
int mini = R;
for(int j=w; j>=0; --j) {
dp[i][j].nd = max(dp[i][j].nd, R-mini);
if(j-1>=0) {
mini = min(mini, grid[i-1][j-1]);
}
}
}
int res = INF;
for(int i=1; i<=w; ++i) {
res = min(res, value(dp[h][i]));
}
return res;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int h, w; cin>>h>>w;
vector<vector<ll>> grid(h, vector<ll>(w));
for(int i=0; i<h; ++i) {
for(int j=0; j<w; ++j) {
cin>>grid[i][j];
}
}
ll ans = INF;
auto G = grid;
ans = min(ans, solve(G));
reverse(G.begin(), G.end());
ans = min(ans, solve(G));
for(int i=0; i<h; ++i) {
reverse(G[i].begin(), G[i].end());
}
ans = min(ans, solve(G));
reverse(G.begin(), G.end());
ans = min(ans, solve(G));
cout<<ans;
}
