#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-3223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int H,W;
int A[2000][2000];
int M = 0;
int m = INT_MAX;

int MM[2000][2001],mm[2000][2001],MM2[2000][2001],mm2[2000][2001],dp[2000][2001][2][2];
int solve(int y, int x, int downway, int Mm){
	if(x == W+1 || x == -1) return INT_MAX;
	if(y == H) return 0;
	if(dp[y][x][downway][Mm] != -1) return dp[y][x][downway][Mm];
	int re = INT_MAX;
	if(downway == 0){
		/*for(int i=x; i<=W; i++){
			if(Mm == 0) re = min(re, max({M-mm[y][i], MM[y][i]-m, solve(y+1,i,downway, Mm)}) );
			else re = min(re, max({MM2[y][i]-m, M-mm2[y][i], solve(y+1,i,downway, Mm)}) );
		}*/
		if(Mm == 0) re = min( max({M-mm[y][x], MM[y][x]-m, solve(y+1,x,downway, Mm)}) , solve(y,x+1,downway,Mm) );
		else re = min( max({MM2[y][x]-m, M-mm2[y][x], solve(y+1,x,downway, Mm)}) , solve(y,x+1,downway,Mm) );
	}
	else{
		/*for(int i=x; i>=0; i--){
			if(Mm == 0) re = min(re, max({M-mm[y][i], MM[y][i]-m, solve(y+1,i,downway, Mm)}) );
			else re = min(re, max({MM2[y][i]-m, M-mm2[y][i], solve(y+1,i,downway, Mm)}) );
		}*/
		if(Mm == 0) re = min( max({M-mm[y][x], MM[y][x]-m, solve(y+1,x,downway, Mm)}) , solve(y,x-1,downway,Mm) );
		else re = min( max({MM2[y][x]-m, M-mm2[y][x], solve(y+1,x,downway, Mm)}) , solve(y,x-1,downway,Mm) );
	}
	
	return dp[y][x][downway][Mm] = re;
}

int main() {
	iostream::sync_with_stdio(false);

	cin >> H >> W;
	for(int i=0; i<H; i++){
		for(int j=0; j<=W; j++){
			dp[i][j][0][0] = -1;
			dp[i][j][0][1] = -1;
			dp[i][j][1][0] = -1;
			dp[i][j][1][1] = -1;
			if(i == H || j == W) continue;
			cin >> A[i][j];
			M = max(M, A[i][j]);
			m = min(m, A[i][j]);
		}
	}

	for(int i=0; i<H; i++){
		mm[i][0] = M;
		MM[i][W] = m;
		MM2[i][0] = m;
		mm2[i][W] = M;
	}
	for(int i=0; i<H; i++){
		for(int j=1; j<=W; j++){
			mm[i][j] = min(mm[i][j-1], A[i][j-1]);
			MM2[i][j] = max(MM2[i][j-1], A[i][j-1]);
		}
		for(int j=W-1; j>=0; j--){
			MM[i][j] = max(MM[i][j+1], A[i][j]);
			mm2[i][j] = min(mm2[i][j+1], A[i][j]);
		}
	}
	/*
	for(int i=0; i<H; i++){
		for(int j=0; j<=W; j++){
			cout << mm[i][j] << " ";
		}
		cout << endl;
	}
	for(int i=0; i<H; i++){
		for(int j=0; j<=W; j++){
			cout << MM[i][j] << " ";
		}
		cout << endl;
	}
	for(int i=0; i<H; i++){
		for(int j=0; j<=W; j++){
			cout << mm2[i][j] << " ";
		}
		cout << endl;
	}
	for(int i=0; i<H; i++){
		for(int j=0; j<=W; j++){
			cout << MM2[i][j] << " ";
		}
		cout << endl;
	}*/

	int ans = INT_MAX;
	ans = min(ans, solve(0, 0, 0, 0));
	ans = min(ans, solve(0, 0, 0, 1));
	ans = min(ans, solve(0, W, 1, 0));
	ans = min(ans, solve(0, W, 1, 1));
	cout << ans << endl;

	return 0;
}

