#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> tab;
int minn, maxx, h, w;
bool spr(int sr)
{
int pop = w - 1;
for(int i = 0; i < h; i++)
{
int gdzie = -1;
for(int j = 0; j <= pop; j++)
{
if(tab[i][j] - minn > sr)
{
//cout << i << " " << j << endl;
j = w + 7;
}
else
{
gdzie = j;
}
}
pop = gdzie;
for(int j = pop + 1; j < w; j++)
{
if(maxx - tab[i][j] > sr)
{
return false;
}
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
minn = INT_MAX;
maxx = INT_MIN;
int odp = INT_MAX;
cin >> h >> w;
tab.resize(h);
for(int i = 0; i < h; i++)
{
tab[i].resize(w);
for(int j = 0; j < w; j++)
{
cin >> tab[i][j];
minn = min(minn, tab[i][j]);
maxx = max(maxx, tab[i][j]);
}
}
//cout << minn << " " << maxx << endl;
//cout << spr(10) << endl;
int l = 0, r = maxx;
while (l < r)
{
int sr = (l + r) / 2;
//cout << spr(sr) << " " << sr << endl;
if (spr(sr))
{
r = sr;
}
else
{
l = sr + 1;
}
}
odp = min(odp, l);
for(int i = 0; i < h; i++)
{
reverse(tab[i].begin(), tab[i].end());
}
l = 0, r = maxx;
while (l < r)
{
int sr = (l + r) / 2;
if (spr(sr))
{
r = sr;
}
else
{
l = sr + 1;
}
}
odp = min(odp, l);
for(int i = 0; i < w; i++)
{
for(int j = 0; j < h / 2; j++)
{
swap(tab[j][i], tab[h - j - 1][i]);
}
}
l = 0, r = maxx;
while (l < r)
{
int sr = (l + r) / 2;
if (spr(sr))
{
r = sr;
}
else
{
l = sr + 1;
}
}
odp = min(odp, l);
for(int i = 0; i < h; i++)
{
reverse(tab[i].begin(), tab[i].end());
}
l = 0, r = maxx;
while (l < r)
{
int sr = (l + r) / 2;
if (spr(sr))
{
r = sr;
}
else
{
l = sr + 1;
}
}
odp = min(odp, l);
cout << odp << endl;
return 0;
}
