#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 2005
#define LOG 17
using namespace std;
const ll inf = 2e9;
bool ghuy4g;
const ll hx[] = {1, -1, 0, 0};
const ll hy[] = {0, 0, 1, -1};
ll h, w, a[N][N], b[N][N], par[N * N], sz[N * N], val, den[N];
bool vst[N][N];
pii mxx;
vector<ll> ns;
/////
///
///
//
//
bool check1(ll mid) {
ll prev = w;
for (int i = 1; i <= mxx.fi; i ++) {
for (int j = 1; j <= mxx.se; j ++) {
if (val - a[i][j] > mid) return 0;
den[i] = j;
}
ll j = mxx.se + 1;
while (j <= prev && val - a[i][j] <= mid) {
den[i] = j;
j ++ ;
}
prev = den[i];
}
for (int i = mxx.fi + 1; i <= h; i ++) {
ll j = 1;
den[i] = 0;
while (j <= prev && val - a[i][j] <= mid) {
den[i] = j;
j ++ ;
}
prev = den[i];
}
ll cmax = -inf, cmin = inf;
for (int i = 1; i <= h; i ++) {
for (int j = den[i] + 1; j <= w; j ++) {
cmax = max(cmax, a[i][j]);
cmin = min(cmin, a[i][j]);
}
}
if (cmax - cmin > mid) return 0;
return 1;
}
//
////
////
////
/////
//////
bool check2(ll mid) {
ll prev = w;
for (int i = h; i >= mxx.fi; i --) {
for (int j = 1; j <= mxx.se; j ++) {
if (val - a[i][j] > mid) return 0;
den[i] = j;
}
ll j = mxx.se + 1;
while (j <= prev && val - a[i][j] <= mid) {
den[i] = j;
j ++ ;
}
prev = den[i];
}
for (int i = mxx.fi - 1; i >= 1; i --) {
ll j = 1;
den[i] = 0;
while (j <= prev && val - a[i][j] <= mid) {
den[i] = j;
j ++ ;
}
prev = den[i];
}
ll cmax = -inf, cmin = inf;
for (int i = 1; i <= h; i ++) {
for (int j = den[i] + 1; j <= w; j ++) {
cmax = max(cmax, a[i][j]);
cmin = min(cmin, a[i][j]);
}
}
if (cmax - cmin > mid) return 0;
return 1;
}
void solve() {
ll ans1 = inf;
ll l = 1, r = 1e9, ans = -1;
while (l <= r) {
ll mid = (l + r) / 2;
if (check1(mid) || check2(mid)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
if (ans != -1) {
ans1 = min(ans1, ans);
}
for (int i = 1; i <= h; i ++) {
for (int j = 1; j <= w; j ++) {
a[i][j] = b[i][w - j + 1];
}
}
for (int i = 1; i <= h; i ++) {
for (int j = 1; j <= w; j ++) {
if (a[i][j] > a[mxx.fi][mxx.se]) {
mxx = {i, j};
}
//cout << a[i][j] << " ";
}
//cout << endl;
}
l = 1, r = 1e9, ans = -1;
while (l <= r) {
ll mid = (l + r) / 2;
//cout << mid << " " << check1(mid) << " " << check2(mid) << endl;
if (check1(mid) || check2(mid)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
//cout << check2(11) << endl;
if (ans != -1) {
ans1 = min(ans1, ans);
}
cout << ans1 << endl;
}
bool klinh;
signed main() {
// freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
//srand(time(0));
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> h >> w;
//cout << get(6).fi << " " << get(6).se << endl;
for (int i = 1; i <= h; i ++) {
for (int j = 1; j <= w; j ++) {
cin >> a[i][j];
b[i][j] = a[i][j];
val = max(val, a[i][j]);
if (a[i][j] > a[mxx.fi][mxx.se]) {
mxx = {i, j};
}
ns.push_back(a[i][j]);
}
}
solve();
cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}
