//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 2000;
int a[N][N];
int bot[N];
int b[N];
int mx;
int solve(int h, int w) {
for (int i = 0; i < h; i++) {
b[i] = -1;
for (int j = 0; j < w; j++) {
if (a[i][j] == mx) {
b[i] = j;
}
}
}
int l = -1, r = 1e9;
while (l + 1 < r) {
int mid = (l + r) / 2;
for (int i = 0; i < h; i++) {
bot[i] = w;
for (int j = 0; j < w; j++) {
if (a[i][j] + mid < mx) {
bot[i] = j;
break;
}
}
}
//decreasing
int d = w - 1;
bool f = true;
int kek1 = mx;
int kek2 = 0;
for (int i = 0; i < h; i++) {
d = min(d, bot[i] - 1);
if (d < b[i]) {
f = false;
break;
}
for (int j = d + 1; j < w; j++) {
kek1 = min(kek1, a[i][j]);
kek2 = max(kek2, a[i][j]);
}
}
if (f && kek2 - kek1 <= mid) {
r = mid;
continue;
}
l = mid;
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int h, w;
cin >> h >> w;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> a[i][j];
mx = max(mx, a[i][j]);
}
}
int ans = solve(h, w);
for (int i = 0; i < h; i++) {
for (int j = 0; j < w / 2; j++) {
swap(a[i][j], a[i][w - j - 1]);
}
}
ans = min(ans, solve(h, w));
for (int j = 0; j < w; j++) {
for (int i = 0; i < h / 2; i++) {
swap(a[i][j], a[h - i - 1][j]);
}
}
ans = min(ans, solve(h, w));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w / 2; j++) {
swap(a[i][j], a[i][w - j - 1]);
}
}
ans = min(ans, solve(h, w));
cout << ans;
return 0;
}
