#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b / __gcd(a,b)
#define I first
#define II second
#define pb push_back
#define ii pair<int,int>
const int INF = 2 * 1e18;
const int N = 2e5 + 1;
const int MOD = 1e9 + 7;
int n, m;
namespace sub1
{
int a[41][41], b[41][41], k;
int main()
{
cin >> k;
vector<ii> s;
for (int i = 0; i < k; i++)
{
int u, v; cin >> u >> v;
s.pb({u, v});
a[u][v] = 1;
}
int ans = INF;
for (int x = 0; x <= 40; x++)
for (int y = 0; y <= 40; y++)
if (x + y <= ans)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) b[i][j] = a[i][j];
for (auto [u, v] : s)
{
int ox = 1, oy = 1;
for (int i = 1; i <= max(x, y) && (ox | oy); i++)
{
if (ox && i <= x)
{
if (u - i == 0 || b[u - i][v] == 1) ox = 0; else
b[u - i][v] = 1;
// if (x == 4 && y == 5) cout << u - i << ' ' << v << '\n';
}
if (oy && i <= y)
{
if (u + i == n + 1 || b[u + i][v] == 1) oy = 0; else
b[u + i][v] = 1;
}
}
}
// if (x == 4 && y == 5)
// {
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= m; j++) cout << (b[i][j]) << (j == m ? '\n' : ' ');
// }
int l = 0, r = 0, mid = 0, ok = 1;
for (int i = 1; i <= n; i++)
{
int last = 0, nxt = m + 1, ok1 = 0;
for (int j = 1; j <= m; j++)
{
if (b[i][j])
{
ok1 = 1;
if (!last) l = max(l, j - 1); else
mid = max(mid, j - last - 1);
last = j;
}
int jj = m - j + 1;
if (b[i][jj])
{
if (nxt == m + 1) r = max(r, nxt - jj - 1); else
mid = max(mid, nxt - jj - 1);
nxt = jj;
}
}
if (!ok1)
{
ok = 0;
break;
}
}
if (ok)
{
mid = max(0ll, mid - l - r);
ans = min(ans, x + y + l + r + mid);
}
// if (ans == 8) cout << x << ' ' << y << '\n';
}
cout << ans;
return 0;
}
}
namespace sub2
{
int a[41][41];
bool cmp(ii x, ii y)
{
if (x.II < y.II) return true; else
if (x.II == y.II) return x.I < y.I;
return false;
}
int main()
{
int k; cin >> k;
vector<ii> s;
for (int i = 1; i <= k; i++)
{
int u, v;
cin >> u >> v;
s.pb({u, v});
}
sort(s.begin(), s.end(), cmp);
int ans = INF;
for (int tt = 0; tt < k; tt++)
{
int x = s[tt].I - 1;
vector<int> t;
for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++) t.pb(max(0ll, s[j].I - x - s[i].I - 1));
t.pb(n - s[i].I);
}
sort(t.begin(), t.end());
t.resize(unique(t.begin(), t.end()) - t.begin());
for (auto y : t)
{
// if (x == 0 && y == 4) cout << "fwefwef" << '\n';
if (x + y > ans) break;
// cout << x << ' ' << y << '\n';
int cur = x + y;
vector<array<int, 3> > p;
vector<array<int, 2> > b;
for (auto [u, v] : s)
{
int l = max(1ll, u - x), r = min(n, u + y);
b.pb({l, r});
p.pb({v, l, r});
}
sort(b.begin(), b.end());
if (b[0][0] != 1) continue;
int R = b[0][1], ok = 1;
for (int i = 1; i < k; i++)
{
if (b[i][0] > R + 1)
{
ok = 0;
break;
} else R = b[i][1];
}
if (!ok || R != n) continue;
int l = 0, r = 0, mid = 0;
for (int i = 0; i < k; i++)
{
int u = p[i][1], v = p[i][2];
for (int j = 0; j < i && (u <= v); j++)
{
int c = p[j][1], d = p[j][2];
if (c <= u && d >= u)
{
mid = max(mid, p[j][0] - p[i][0] - 1);
u = d + 1;
} else
if (c <= v && d >= v)
{
mid = max(mid, p[j][0] - p[i][0] - 1);
v = c - 1;
}
}
if (u <= v) l = max(l, p[i][0] - 1);
}
for (int i = k - 1; i >= 0; i--)
{
int u = p[i][1], v = p[i][2];
for (int j = i + 1; j < k && (u <= v); j++)
{
int c = p[j][1], d = p[j][2];
if (c <= u && d >= u)
{
mid = max(mid, p[j][0] - p[i][0] - 1);
u = d + 1;
} else
if (c <= v && d >= v)
{
mid = max(mid, p[j][0] - p[i][0] - 1);
v = c - 1;
}
}
// if (mid == 2 && !x && y == 4) cout << i << '\n';
if (u <= v) r = max(r, m - p[i][0]);
}
cur += l + r + max(0ll, mid - l - r);
// if (x == 0 && y == 4) cout << l << ' ' << r << ' ' << mid << '\n';
ans = min(ans, cur);
}
}
cout << ans << '\n';
return 0;
}
}
int32_t main()
{
#define TASKNAME ""
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(TASKNAME".inp","r" ))
{
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".ans","w",stdout);
}
cin >> n >> m;
if (max(n, m) <= 40) sub1 :: main(); else
sub2 :: main();
return 0;
}
