#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2000 + 1;
int n, m, minn = 2e9, maxx = 0;
int mat[MAX_N][MAX_N], lin[MAX_N];
bool check( int x ) {
int last;
bool sePoate;
sePoate = true;
last = n;
for ( int c = 0; c < m; c++ ) {
int l = 0;
while ( l < last && mat[l][c] - minn <= x )
l++;
last = l;
for ( ; l < n; l++ ) {
if ( maxx - mat[l][c] > x )
sePoate = false;
}
}
if ( sePoate )
return true;
sePoate = true;
last = n;
for ( int c = m - 1; c >= 0; c-- ) {
int l = 0;
while ( l < last && mat[l][c] - minn <= x )
l++;
last = l;
for ( ; l < n; l++ ) {
if ( maxx - mat[l][c] > x )
sePoate = false;
}
}
if ( sePoate )
return true;
last = n;
sePoate = true;
for ( int c = 0; c < m; c++ ) {
int l = 0;
while ( l < last && maxx - mat[l][c] <= x )
l++;
last = l;
for ( ; l < n; l++ ) {
if ( mat[l][c] - minn > x )
sePoate = false;
}
}
if ( sePoate )
return true;
last = n;
sePoate = true;
for ( int c = m - 1; c >= 0; c-- ) {
int l = 0;
while ( l < last && maxx - mat[l][c] <= x )
l++;
last = l;
for ( ; l < n; l++ ) {
if ( mat[l][c] - minn > x )
sePoate = false;
}
}
if ( sePoate )
return true;
return false;
}
int main() {
cin >> n >> m;
for ( int l = 0; l < n; l++ ) {
for ( int c = 0; c < m; c++ ) {
cin >> mat[l][c];
minn = min( minn, mat[l][c] );
maxx = max( maxx, mat[l][c] );
}
}
int l = -1, r = maxx - minn;
while ( r - l > 1 ) {
int mid = (l + r) / 2;
if ( check( mid ) )
r = mid;
else
l = mid;
}
cout << r;
return 0;
}
