#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <list>
#include <set>
#include <cassert>
using namespace std;
int nbLigs, nbCols;
vector<pair<int, int>> points;
struct pfile {
int deb, fin;
pair<long long, int> elems[1000];
inline void vide() {
deb = fin = 0;
}
inline void ajoute(long long date, int val) {
while(deb != fin && elems[fin - 1].second <= val) {
fin--;
}
elems[fin++] = {date, val};
}
inline int taille() {
return fin - deb;
}
inline void supprime(long long date) {
while(deb != fin && elems[deb].first <= date)
deb++;
}
inline int maximum() {
if(deb == fin)
return 2000*1000*1000;
return elems[deb].second;
}
};
struct max_ecart {
map<int, int> positions;
priority_queue<pair<int, int>> ecarts;
max_ecart() {
positions[-1]++;
positions[nbLigs]++;
ecarts.push({nbLigs + 1, -1});
}
int tr(int dist) {
if(dist == nbLigs)
return 2000 * 1000 * 1000;
return dist;
}
void ajoute(int pos) {
auto it = positions.lower_bound(pos);
int deb, fin;
fin = it->first;
it--;
deb = it->first;
positions[pos]++;
ecarts.push({fin - pos, pos});
ecarts.push({pos - deb, deb});
}
int minN() {
auto it = positions.begin();
it++;
return tr(it->first);
}
int minS() {
auto it = positions.rbegin();
it++;
return tr(nbLigs - it->first - 1);
}
int minTot() {
while(!ecarts.empty()) {
pair<int, int> t = ecarts.top();
if(positions.find(t.second) != positions.end() && positions.upper_bound(t.second)->first == t.first + t.second) {
return tr(t.first - 1);
}
else {
ecarts.pop();
}
}
return 2000 * 1000 * 1000;
}
};
struct Inter {
long long taille;
int minN, minS, minTot;
};
Inter dyn_inters[300][300];
void precalcule_ecarts() {
for(int iDeb = 0;iDeb < (int)points.size();iDeb++) {
max_ecart curEcarts;
for(int iFin = iDeb;iFin < (int)points.size();iFin++) {
curEcarts.ajoute(points[iFin].first);
Inter nouv;
nouv.minN = curEcarts.minN();
nouv.minS = curEcarts.minS();
nouv.minTot = curEcarts.minTot();
dyn_inters[iDeb][iFin] = nouv;
}
}
}
pfile minS, minN, minTot;
long long traite(long long dist) {
vector<Inter> intervalles;
Inter debut;
debut.minN = debut.minS = debut.minTot = 2000 * 1000 * 1000;
intervalles.push_back(debut);
long long derDeb = -1000 * 1000 * 1000;
int debInd = 0, finInd = 0;
int iDebut = 0, iFin = 0;
while(iDebut != (int)points.size() || iFin != (int)points.size()) {
long long minTemps = (long long)4000 * 1000 * 1000;
if(iDebut != (int)points.size())
minTemps = min<long long>(minTemps, points[iDebut].second);
if(iFin != (int)points.size())
minTemps = min<long long>(minTemps, points[iFin].second + dist);
intervalles.back().taille = minTemps - derDeb;
derDeb = minTemps;
while(iDebut != (int)points.size() && points[iDebut].second == minTemps) {
finInd++;
iDebut++;
}
while(iFin != (int)points.size() && points[iFin].second + dist == minTemps) {
debInd++;
iFin++;
}
Inter nouv;
if(debInd == finInd) {
nouv.minS = nouv.minN = nouv.minTot = 1000 * 1000 * 1000;
}
else {
nouv = dyn_inters[debInd][finInd - 1];
}
intervalles.push_back(nouv);
}
intervalles.back().taille = 1000 * 1000 * 1000;
long long minPrix = 2000 * 1000 * 1000;
long long posFin = 0, posDeb = 0;
int fin = 1;
minS.vide();
minN.vide();
minTot.vide();
for(int deb = 1;fin < (int)intervalles.size() - 1;) {
if(posFin - posDeb < nbCols) {
posFin += intervalles[fin].taille;
minS.ajoute(posFin, intervalles[fin].minS);
minN.ajoute(posFin, intervalles[fin].minN);
minTot.ajoute(posFin, intervalles[fin].minTot);
fin++;
}
if(posFin - posDeb >= nbCols) {
minPrix = min<long long>(minPrix, max(minS.maximum() + minN.maximum(), minTot.maximum()));
posDeb += intervalles[deb].taille;
minS.supprime(posDeb);
minN.supprime(posDeb);
minTot.supprime(posDeb);
deb++;
}
}
return minPrix + dist - 1;
}
int main() {
ios_base::sync_with_stdio(false);
cin >> nbCols >> nbLigs;
int nbPoints;
cin >> nbPoints;
for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
int lig, col;
cin >> lig >> col;
points.push_back({col - 1, lig - 1});
}
sort(points.begin(), points.end(), [](const pair<int, int>&a, const pair<int, int>&b){return a.second < b.second;});
set<int> distancesCol;
distancesCol.insert(1);
distancesCol.insert(nbCols);
distancesCol.insert(2 * nbCols);
for(int iPointA = 0;iPointA < nbPoints;iPointA++) {
for(int iPointB = 0;iPointB < nbPoints;iPointB++) {
distancesCol.insert(abs(points[iPointA].second - points[iPointB].second));
distancesCol.insert(abs(nbCols - points[iPointA].second + points[iPointB].second));
}
}
precalcule_ecarts();
long long minTotal = 2000 * 1000 * 1000;
for(int dist : distancesCol) {
if(dist >= 1) {
minTotal = min(minTotal, traite(dist));
}
}
cout << minTotal << endl;
return 0;
}
