#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 2e9; void solve(){ int n, m; cin >> n >> m; vector<vector<int>> a(n+1, vector<int>(m+1)); int S = INF, L = -INF; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> a[i][j]; S = min(S, a[i][j]); L = max(L, a[i][j]); } } auto rtate = [&](vector<vector<int>> &a) -> void{ int n = a.size()-1, m = a[0].size()-1; vector<vector<int>> b(m+1, vector<int>(n+1)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ b[j][n-i+1] = a[i][j]; } } a = b; }; int ans = INF; auto sf = [&]() -> int{ int n = a.size() - 1, m = a[0].size()-1; vector<int> f(m+1, INF), pf(m+1, INF); vector<int> pfa(m+1, 0), sfa(m+2, 0); vector<int> rS(n+1, 0), lL(n+1, m+1); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(a[i][j] == S){ rS[i] = max(rS[i], j); } if(a[i][j] == L){ lL[i] = min(lL[i], j); } } } f[0] = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ pfa[j] = max(pfa[j-1], a[i][j] - S); } for(int j = m; j >= 1; j--){ sfa[j] = max(sfa[j+1], L - a[i][j]); } pf[0] = f[0]; f[0] = INF; for(int j = 1; j <= m; j++){ pf[j] = min(pf[j-1], f[j]); f[j] = INF; } for(int j = rS[i]; j < lL[i]; j++){ f[j] = max(pf[j], max(pfa[j], sfa[j+1])); } } int res = INF; for(int j = 1; j <= m; j++){ res = min(res, f[j]); } return res; }; for(int it = 0; it < 4; it++){ if(it > 0){ rtate(a); } ans = min(ans, sf()); } cout << ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }