#include <bits/stdc++.h>
using namespace std;
const int N = 2001;
int prefix[N], suffix[N], diff[N][N], a[N][N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int maxi = INT_MIN, mini = INT_MAX;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
maxi = max(maxi, a[i][j]);
mini = min(mini, a[i][j]);
}
}
fill(diff[0], diff[0] + m + 1, INT_MIN);
int ans = INT_MAX;
for (int k = 0; k < 2; ++k) {
for (int i = 0; i < n; ++i) {
reverse(a[i], a[i] + m);
}
for (int l = 0; l < 2; ++l) {
reverse(a, a + n);
for (int i = 0; i < n; ++i) {
copy(a[i], a[i] + m, prefix);
for (int j = 1; j < m; ++j) {
prefix[j] = min(prefix[j], prefix[j - 1]);
}
copy(a[i], a[i] + m, suffix);
for (int j = m - 2; j >= 0; --j) {
suffix[j] = max(suffix[j], suffix[j + 1]);
}
for (int j = 0; j <= m; ++j) {
diff[i + 1][j] = max({
j > 0 ? maxi - prefix[j - 1] : INT_MIN,
j < m ? suffix[j] - mini : INT_MIN,
diff[i][j]
});
if (j > 0) {
diff[i + 1][j] = min(diff[i + 1][j], diff[i + 1][j - 1]);
}
}
}
ans = min(ans, *min_element(diff[n], diff[n] + m + 1));
}
}
cout << ans << "\n";
}
