#pragma GCC optimize "O3,inline,unroll-loops,omit-frame-pointer"
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <utility>
using namespace std;
using ll = long long;
const int oo = 2*1000*1000*1000 + 42;
const int NB_MAX_CELLULES_PLEINES = 300;
const int NB_MAX_EVENEMENTS = 4*NB_MAX_CELLULES_PLEINES;
int nbLignes, nbColonnes;
int nbCellulesPleines;
pair<int, int> cellulesPleines[NB_MAX_CELLULES_PLEINES];
struct Evenement
{
bool estDebut;
bool estPourOuvertureFenetre;
uint iColonne;
uint iLigne;
bool operator< (const Evenement &autre) const
{
if (iColonne != autre.iColonne) {
return iColonne < autre.iColonne;
}
if (estDebut != autre.estDebut) {
return estDebut;
}
if (iLigne != autre.iLigne) {
return iLigne < autre.iLigne;
}
return estPourOuvertureFenetre < autre.estPourOuvertureFenetre;
}
};
const int NB_ETIREMENTS = 3;
const int ETIREMENT_HAUT = 0;
const int ETIREMENT_BAS = 1;
const int ETIREMENT_MILIEU = 2;
struct Colonne
{
map<int, int> nbRecouvrements; // pour chaque ligne
multiset<int> longueursVides; // Entre deux cellules pleines ou en haut ou en bas
Colonne ()
{
longueursVides.insert(nbLignes);
}
inline void appliquerEvenement (const Evenement &evenement)
{
/*cerr << "Nouvel evenement: " << evenement.iLigne << " " << evenement.estDebut << endl;
cerr << "Longueurs: ";
for (auto l : longueursVides) {
cerr << l << " ";
}
cerr << endl;
cerr << "Nb recouvrements: ";
for (auto p : nbRecouvrements) {
cerr << "(" << p.first << " " << p.second << ") ";
}
cerr << endl;*/
if (evenement.estDebut) {
nbRecouvrements[evenement.iLigne]++;
}
map<int, int>::iterator nbRecouvrementsLigne = nbRecouvrements.find(evenement.iLigne);
int iDebut = 0;
if (nbRecouvrementsLigne != nbRecouvrements.begin()) {
nbRecouvrementsLigne--;
iDebut = nbRecouvrementsLigne->first + 1;
nbRecouvrementsLigne++;
}
int iFin = nbLignes;
nbRecouvrementsLigne++;
if (nbRecouvrementsLigne != nbRecouvrements.end()) {
iFin = nbRecouvrementsLigne->first;
}
nbRecouvrementsLigne--;
if (evenement.estDebut) {
if (nbRecouvrementsLigne->second == 1) {
longueursVides.erase(longueursVides.find(iFin - iDebut)); // Supprime une seule occurence
longueursVides.insert(evenement.iLigne - iDebut);
longueursVides.insert(iFin - evenement.iLigne - 1);
}
}
else {
nbRecouvrementsLigne->second--;
if (nbRecouvrementsLigne->second == 0) {
nbRecouvrements.erase(nbRecouvrementsLigne);
longueursVides.insert(iFin - iDebut);
longueursVides.erase(longueursVides.find(evenement.iLigne - iDebut));
longueursVides.erase(longueursVides.find(iFin - evenement.iLigne - 1));
}
}
}
inline bool estVide () const
{
return nbRecouvrements.empty();
}
inline int nbEtirementsHaut () const
{
if (nbRecouvrements.empty()) {
return +oo;
}
return nbRecouvrements.begin()->first;
}
inline int nbEtirementsBas () const
{
if (nbRecouvrements.empty()) {
return +oo;
}
return nbLignes - nbRecouvrements.rbegin()->first - 1;
}
inline int nbEtirementsMilieu () const
{
if (estVide()) {
return +oo;
}
if (longueursVides.empty()) {
return 0;
}
return *longueursVides.rbegin();
}
inline int nbEtirements (const int iEtirement) const
{
if (iEtirement == ETIREMENT_HAUT) {
return nbEtirementsHaut();
}
if (iEtirement == ETIREMENT_BAS) {
return nbEtirementsBas();
}
return nbEtirementsMilieu();
}
};
Evenement evenements[NB_MAX_EVENEMENTS];
int getNbEtirementsVerticauxMin (const uint nbDroite)
{
int nbEvenements = 0;
for (int iCellulePleine=0; iCellulePleine<nbCellulesPleines; iCellulePleine++) {
const uint iLigne = cellulesPleines[iCellulePleine].first;
const uint iColonne = cellulesPleines[iCellulePleine].second;
evenements[nbEvenements++] = Evenement{true, true, iColonne, iLigne};
evenements[nbEvenements++] = Evenement{false, true, iColonne+nbDroite+1, iLigne};
evenements[nbEvenements++] = Evenement{true, false, iColonne + nbColonnes, iLigne};
evenements[nbEvenements++] = Evenement{false, false, iColonne+nbDroite+1 + nbColonnes, iLigne};
}
sort(evenements, evenements+nbEvenements);
int nbEtirementsMin = +oo;
Colonne debutFenetre;
Colonne finFenetre;
int nbColonnesVides = nbColonnes;
map<int, int> nbOccurencesEtirements[NB_ETIREMENTS];
for (int iEtirement=0; iEtirement<NB_ETIREMENTS; iEtirement++) {
nbOccurencesEtirements[iEtirement][+oo] = nbColonnes;
}
for (int iEvenement=0; iEvenement<nbEvenements; iEvenement++) {
// Mettre à jour le meilleur
if (nbColonnesVides == 0) {
map<int, int>::iterator it;
it = nbOccurencesEtirements[ETIREMENT_HAUT].end();
it--;
const int nbHaut = it->first;
it = nbOccurencesEtirements[ETIREMENT_BAS].end();
it--;
const int nbBas = it->first;
it = nbOccurencesEtirements[ETIREMENT_MILIEU].end();
it--;
const int nbMilieu = it->first;
const int nbEtirements = nbHaut + nbBas + max(nbMilieu - nbHaut - nbBas, 0);
nbEtirementsMin = min(nbEtirements, nbEtirementsMin);
}
// Appliquer l'événement
const Evenement &evenement = evenements[iEvenement];
if (evenement.estPourOuvertureFenetre) {
debutFenetre.appliquerEvenement(evenement);
}
else {
finFenetre.appliquerEvenement(evenement);
}
// Avancer
if (iEvenement < nbEvenements-1 && evenements[iEvenement+1].iColonne != evenement.iColonne) {
const int distAAvancer = evenements[iEvenement+1].iColonne - evenement.iColonne;
if (debutFenetre.estVide()) {
nbColonnesVides += distAAvancer;
}
if (finFenetre.estVide()) {
nbColonnesVides -= distAAvancer;
}
for (int iEtirement=0; iEtirement<NB_ETIREMENTS; iEtirement++) { // HAUT, BAS, MILIEU
nbOccurencesEtirements[iEtirement][debutFenetre.nbEtirements(iEtirement)] += distAAvancer;
nbOccurencesEtirements[iEtirement][finFenetre.nbEtirements(iEtirement)] -= distAAvancer;
if (nbOccurencesEtirements[iEtirement][finFenetre.nbEtirements(iEtirement)] == 0) {
nbOccurencesEtirements[iEtirement].erase(finFenetre.nbEtirements(iEtirement));
}
}
}
}
return nbEtirementsMin;
}
int main ()
{
scanf("%d %d", &nbLignes, &nbColonnes);
scanf("%d", &nbCellulesPleines);
for (int iCellule=0; iCellule<nbCellulesPleines; iCellule++) {
int iLigne, iColonne;
scanf("%d %d", &iLigne, &iColonne);
iLigne--, iColonne--;
cellulesPleines[iCellule] = make_pair(iLigne, iColonne);
}
int iColonneMin = +oo;
int iColonneMax = 0;
for (int iCellulePleine=0; iCellulePleine<nbCellulesPleines; iCellulePleine++) {
const pair<int, int> &cellule = cellulesPleines[iCellulePleine];
iColonneMin = min(cellule.second, iColonneMin);
iColonneMax = max(cellule.second, iColonneMax);
}
set<int> nbDroitesPossibles;
nbDroitesPossibles.insert(0);
ll nbEtirementsMin = +oo;
for (int iCellule1=0; iCellule1<nbCellulesPleines; iCellule1++) {
const int iColonne1 = cellulesPleines[iCellule1].second;
nbDroitesPossibles.insert(iColonne1); // Depuis la gauche vers la cellule actuelle
nbDroitesPossibles.insert(nbColonnes - iColonne1 - 1);
nbDroitesPossibles.insert(iColonneMin + (nbColonnes - iColonne1 - 1));
for (int iCellule2=0; iCellule2<nbCellulesPleines; iCellule2++) {
const int iColonne2 = cellulesPleines[iCellule2].second;
if (iColonne2 > iColonne1) {
nbDroitesPossibles.insert(iColonne2 - iColonne1 - 1);
nbDroitesPossibles.insert(iColonneMin + (iColonne2 - iColonne1 - 1));
}
}
}
for (int nbDroite : nbDroitesPossibles) {
const ll nbEtirements = (ll)nbDroite + getNbEtirementsVerticauxMin(nbDroite);
nbEtirementsMin = min(nbEtirements, nbEtirementsMin);
}
printf("%lld\n", nbEtirementsMin);
#if 0
int nbDroite = 0;
int nbEtirementsVerticauxMin = getNbEtirementsVerticauxMin(nbDroite);
ll nbEtapesMin = nbEtirementsVerticauxMin;
while (nbEtirementsVerticauxMin != getNbEtirementsVerticauxMin(2*nbColonnes)) {
const int nbEtirements = nbEtirementsVerticauxMin;
ll debut = 0;
ll fin = 2*nbColonnes;
while (fin - debut > 1) {
const ll milieu = (debut + fin) / 2;
if (getNbEtirementsVerticauxMin(milieu) < nbEtirements) {
fin = milieu;
}
else {
debut = milieu;
}
}
nbDroite = fin;
nbEtirementsVerticauxMin = getNbEtirementsVerticauxMin(nbDroite);
const ll nbEtapes = (ll)nbEtirementsVerticauxMin + nbDroite;
nbEtapesMin = min(nbEtapes, nbEtapesMin);
}
printf("%lld\n", nbEtapesMin);
#endif
return 0;
}
