#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef set<pll> spll;
typedef pair<pll, ll> ppll_ll;
typedef set<ppll_ll> sppll_ll;
typedef set<ll> sll;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define sz(a) (ll) a.size()
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define trav(itr, a, t) for (t::iterator itr = a.begin(); itr != a.end())
// coordinate convention (y, x) for (n, m)
const pll delta[4] = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1)};
ll n, m, d;
vvll ice;
bool inline is_edge(const pll& pos) {return (pos.first == 0) || (pos.first == n - 1) || (pos.second == 0) || (pos.second == m - 1);}
ll inline coco(pll z) {return z.first + (z.second * n);}
pll inline rev_coco(ll z) {return mp(z % n, z / n);}
pll inline operator+(const pll& lhs, const pll& rhs) {return mp(lhs.first + rhs.first, lhs.second + rhs.second);}
pll inline operator+(const pll& lhs, const ll& rhs) {return mp(lhs.first + rhs, lhs.second);}
sppll_ll best_edges; // ((d[neigh] + cnt, neigh), src)
spll best_comp; // (cnt, src)
struct component;
vector<component> comps;
vll par;
ll find_par(ll x) {
if (x != par[x]) par[x] = find_par(par[x]);
return par[x];
}
struct component {
ll root;
ll cnt;
spll edges; // (d[neigh], neigh)
//sll members;
component(ll root) : root(root), cnt(1) {
par[root] = root;
//members.insert(root);
}
ppll_ll best_edge() {
return mp(*edges.rbegin() + cnt, root);
}
void add_best_edge() {
if (sz(edges)) best_edges.insert(best_edge());
}
void absorb(ll oth) {
//cout << "root " << root << endl;
if (sz(edges)) best_edges.erase(best_edge()); // remove previous best edge
best_comp.erase(mp(cnt, root));
//cout << oth << " -> " << find_par(oth) << endl;
oth = find_par(oth);
if (sz(comps[oth].edges)) best_edges.erase(comps[oth].best_edge()); // remove previous best edge from oth
best_comp.erase(mp(comps[oth].cnt, oth));
par[oth] = root;
cnt += comps[oth].cnt;
//cout << "cnt -> " << cnt << " (+" << comps[oth].cnt << ")" << endl;
edges.insert(comps[oth].edges.begin(), comps[oth].edges.end()); // merge edges
add_best_edge(); // make public best edge
best_comp.insert(mp(cnt, root));
}
void tick() {
best_edges.erase(best_edge());
edges.erase(prev(edges.end()));
add_best_edge();
}
};
spll e;
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> m;
d = 1;
ice.resize(n);
rep(i, 0, n) {
ice[i].resize(m);
rep(j, 0, m) {
cin >> ice[i][j];
d = max<ll>(d, ice[i][j]);
}
}
par.resize(n * m);
//comps.reserve(n * m);
rep(j, 0, m) {
rep(i, 0, n) {
comps.pb(component(coco(mp(i, j))));
}
}
rep(i, 0, n) {
rep(j, 0, m) {
// initialize neighbors
rep(d, 0, 4) {
pll neigh = mp(i, j) + delta[d];
if ((neigh.first == -1) || (neigh.first == n) || (neigh.second == -1) || (neigh.second == m)) continue; // check oob
// add edge (i, j) -> neigh (with d = ice[neigh])
//cout << "edge: " << coco(mp(i, j)) << " -> (" << ice[neigh.first][neigh.second] << ", " << coco(neigh) << ")" << endl;
comps[coco(mp(i, j))].edges.insert(mp(ice[neigh.first][neigh.second], coco(neigh)));
}
if (is_edge(mp(i, j))) {
e.insert(mp(ice[i][j], coco(mp(i, j));
}
/* if (is_edge(mp(i, j))) { // now we only consider edges from active...
// initialize presence in best_edges and best_comp
comps[coco(mp(i, j))].add_best_edge();
best_comp.insert(mp(1, coco(mp(i, j))));
} */
}
}
/* cout << "par:" << endl;
rep(i, 0, n) {
rep(j, 0, m) {
cout << par[coco(mp(i, j))] << " ";
}
cout << endl;
} */
d++;
while ((best_comp.empty()) || (best_comp.rbegin()->first < d)) {
//rep(tmp, 0, 20) {
//cout << "d = " << d << endl;
//if (!best_comp.empty()) cout << "comp: " << best_comp.rbegin()->first << " " << best_comp.rbegin()->second << endl;
//if (!best_edges.empty()) cout << "edge: " << best_edges.rbegin()->first.first << " " << best_edges.rbegin()->first.second << " " << best_edges.rbegin()->second << endl;
// check for edges to add
if ((!best_edges.empty()) && (best_edges.rbegin()->first.first >= d)) {
// do some pre-work
ll src = best_edges.rbegin()->second;
ll dest = best_edges.rbegin()->first.second;
// check if edge goes from comp to itself
if (find_par(dest) == src) {
//cout << "tick" << endl;
comps[src].tick(); // remove best edge, because it goes within itself
} else { // the edge merges two distinct components
//cout << "absorb" << endl;
comps[src].absorb(dest);
}
} else { // if no edges, then decrement d
d--;
while ((!e.empty()) && (e.rbegin()->first == d)) {
if (find_par(e.rbegin()->second) == e.rbegin()->second) {
comps[e.rbegin()->second].add_best_edge();
best_comp.insert(mp(1, e.rbegin()->second));
}
e.erase(prev(e.end()));
}
/* // activate all edges with ice = d
rep(i, 0, n) {
rep(j, 0, m) {
if (is_edge(mp(i, j)) && (find_par(coco(mp(i, j))) == coco(mp(i, j)))) {
if (ice[i][j] == d) {
// initialize presence in best_edges and best_comp
comps[coco(mp(i, j))].add_best_edge();
best_comp.insert(mp(1, coco(mp(i, j))));
}
}
}
} */
}
/* cout << "par:" << endl;
rep(i, 0, n) {
rep(j, 0, m) {
cout << par[coco(mp(i, j))] << " ";
}
cout << endl;
} */
}
cout << d << endl;
return 0;
}