#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << "No"; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr
const int N = 2007;
int f[N][N], up[N];
int calc_ans(int n, int m, int mn, int mx) {
up[0] = n + 1;
loop1(j, m) {
up[j] = n + 1;
loop1(i, n) {
if (f[i][j] == mx) {
up[j] = i; break;
}
}
}
loop1(j, m)
up[j] = min(up[j], up[j - 1]);
int cur = 0;
loop1(j, m)
for (int i = up[j]; i <= n; ++i)
cur = max(cur, mx - f[i][j]);
int l = cur - 1, r = mx - mn;
while (r - l > 1) {
int mid = l + r >> 1;
bool flag = 1;
int cur = 1;
for (int j = m; j > 0; --j) {
int i = up[j] - 1;
for (; i >= cur && mx - f[i][j] <= mid; --i);
loop1(k, i)
if (f[k][j] - mn > mid)
flag = 0;
cur = i + 1;
}
if (flag)
r = mid;
else
l = mid;
}
return r;
}
void solve() {
int n, m;
cin >> n >> m;
int mx = 0, mn = 1000000000;
loop1(i, n) {
loop1(j, m) {
cin >> f[i][j];
mn = min(mn, f[i][j]);
mx = max(mx, f[i][j]);
}
}
int ans = calc_ans(n, m, mn, mx);
loop1(j, m)
loop1(i, n / 2)
swap(f[i][j], f[n - i + 1][j]);
ans = min(ans, calc_ans(n, m, mn, mx));
loop1(i, n)
loop1(j, m / 2)
swap(f[i][j], f[i][m - j + 1]);
ans = min(ans, calc_ans(n, m, mn, mx));
loop1(j, m)
loop1(i, n / 2)
swap(f[i][j], f[n - i + 1][j]);
ans = min(ans, calc_ans(n, m, mn, mx));
cout << ans;
}
signed main() {
//freopen("dream.in", "r", stdin);
//freopen("dream.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//int t; cin >> t; loop(i, t)
solve();
return 0;
}
