#include<bits/stdc++.h>
using namespace std;
const int N = (int)2e3 + 5, M = N, inf = (int)1e9 + 123;
int n, m, a[N][M], mnA = inf, mxA = -inf, sumMn[N][M], sumMx[N][M];
bool check1 () {
for (int prv = 0, i = 1; i <= n; ++i) {
int nxt = -1;
for (int j = prv; j <= m; ++j) {
if (sumMn[i][j] == j && sumMx[i][m] - sumMx[i][j] == m - j) { nxt = j; break ; }
}
if (nxt == -1) return false;
prv = nxt;
}
return true;
}
bool check2 () {
for (int prv = 0, i = 1; i <= n; ++i) {
int nxt = -1;
for (int j = prv; j <= m; ++j) {
if (sumMx[i][j] == j && sumMn[i][m] - sumMn[i][j] == m - j) { nxt = j; break ; }
}
if (nxt == -1) return false;
prv = nxt;
}
return true;
}
bool check3 () {
for (int prv = m, i = 1; i <= n; ++i) {
int nxt = -1;
for (int j = prv; j >= 0; --j) {
if (sumMn[i][j] == j && sumMx[i][m] - sumMx[i][j] == m - j) { nxt = j; break ; }
}
if (nxt == -1) return false;
prv = nxt;
}
return true;
}
bool check4 () {
for (int prv = m, i = 1; i <= n; ++i) {
int nxt = -1;
for (int j = prv; j >= 0; --j) {
if (sumMx[i][j] == j && sumMn[i][m] - sumMn[i][j] == m - j) { nxt = j; break ; }
}
if (nxt == -1) return false;
prv = nxt;
}
return true;
}
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
mnA = min(mnA, a[i][j]);
mxA = max(mxA, a[i][j]);
}
}
int lAns = 0, rAns = mxA - mnA;
while (lAns < rAns) {
int mid = (lAns + rAns) >> 1;
memset(sumMn, 0, sizeof sumMn);
memset(sumMx, 0, sizeof sumMx);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
sumMn[i][j] = sumMn[i][j - 1];
sumMx[i][j] = sumMx[i][j - 1];
if (a[i][j] - mnA <= mid) ++sumMn[i][j];
if (mxA - a[i][j] <= mid) ++sumMx[i][j];
}
}
if (check1() || check2() || check3() || check4() ) rAns = mid;
else lAns = mid + 1;
}
cout << lAns;
return 0;
}
