#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INFINI=1000*1000*1000+6,TAILLE_MAX=200*1000+5,COORD_MAX=1000+5;
int nbPoints,maxX,nbImpair;
pair<int,int> initPoint[TAILLE_MAX];
pair<int,int> points[TAILLE_MAX];
int cumu[COORD_MAX][COORD_MAX];
int emboite[TAILLE_MAX];
set<pair<int,int>> enCours;
void fusion(int deb,int fin) {
set<pair<int,int>>::iterator it;
enCours.insert({deb,fin});
nbImpair+=(fin-deb)%2;
it=enCours.lower_bound({fin,-INFINI});
int nouvDeb,nouvFin;
if ((*it).first==fin) {
nbImpair-=((*it).second-(*it).first)%2;
nbImpair-=(fin-deb)%2;
nouvFin=(*it).second;
enCours.erase(it);
it=enCours.lower_bound({deb,fin});
enCours.erase(it);
fin=nouvFin;
enCours.insert({deb,fin});
nbImpair+=(fin-deb)%2;
}
it=enCours.lower_bound({deb,fin});
it--;
if ((*it).second==deb) {
nbImpair-=((*it).second-(*it).first)%2;
nbImpair-=(fin-deb)%2;
nouvDeb=(*it).first;
enCours.erase(it);
it=enCours.lower_bound({deb,fin});
enCours.erase(it);
deb=nouvDeb;
enCours.insert({deb,fin});
nbImpair+=(fin-deb)%2;
}
}
void suppr(int deb,int fin) {
set<pair<int,int>>::iterator it=enCours.lower_bound({deb,fin});
if ((*it).first==deb) {
if ((*it).second==fin) {
nbImpair-=(fin-deb)%2;
enCours.erase(it);
}
else {
nbImpair-=((*it).second-deb)%2;
deb=fin;
fin=(*it).second;
enCours.erase(it);
nbImpair+=(fin-deb)%2;
enCours.insert({deb,fin});
}
}
else {
it--;
if ((*it).second==fin) {
nbImpair-=(fin-(*it).first)%2;
fin=deb;
deb=(*it).first;
enCours.erase(it);
nbImpair+=(fin-deb)%2;
enCours.insert({deb,fin});
}
else {
int premDeb=(*it).first,dernFin=(*it).second;
nbImpair-=(dernFin-premDeb)%2;
enCours.erase(it);
enCours.insert({premDeb,deb});
enCours.insert({fin,dernFin});
nbImpair+=(deb-premDeb)%2;
nbImpair+=(dernFin-fin)%2;
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>nbPoints>>maxX;
int xNouv,yNouv,posMin=0,xMin=INFINI,yMin=INFINI,maxY=0,somX=0;
for (int i=0;i<nbPoints;i++) {
cin>>xNouv>>yNouv;
if (xNouv<xMin or (xNouv==xMin and yNouv<yMin)) {
posMin=i;
xMin=xNouv;
yMin=yNouv;
}
maxY=max(maxY,yNouv);
somX+=xNouv%2;
initPoint[i]={xNouv,yNouv};
}
int posCour,direc=-1,nbPris=1;
points[0]={xMin,yMin};
for (int i=1;i<=nbPoints;i++) {
//cout<<direc<<" "<<nbPris<<endl;
posCour=(posMin+i)%nbPoints;
if (points[nbPris-1].first==initPoint[posCour].first) {
if (direc==0) {
points[nbPris-1].second=initPoint[posCour].second;
//cout<<0<<" "<<initPoint[posCour].first<<" "<<initPoint[posCour].second<<endl;
}
else {
direc=0;
points[nbPris]=initPoint[posCour];
nbPris++;
}
}
else {
if (direc==1) {
//cout<<1<<" "<<initPoint[posCour].first<<" "<<initPoint[posCour].second<<endl;
points[nbPris-1].first=initPoint[posCour].first;
}
else {
direc=1;
points[nbPris]=initPoint[posCour];
nbPris++;
}
}
}
nbPoints=nbPris;
if (direc==0) {
//cout<<"RETOURNE"<<endl;
for (int i=0;i<nbPoints/2;i++) {
swap(points[i],points[nbPoints-1-i]);
}
}
/*for (int i=0;i<nbPoints;i++) {
cout<<points[i].first<<" "<<points[i].second<<endl;
}*/
if (somX==0) {
vector<tuple<int,int,int>> somTri;
for (int i=0;i<nbPoints-1;i++) {
somTri.push_back(make_tuple(points[i].first,points[i].second,i));
}
somTri.push_back(make_tuple(INFINI,INFINI,nbPoints));
sort(somTri.begin(),somTri.end());
enCours.insert({-INFINI,-42});
enCours.insert({INFINI,42});
for (int i=0;i<nbPoints-1;i+=2) {
if (get<2>(somTri[i])<get<2>(somTri[i+1])) {
fusion(get<1>(somTri[i]),get<1>(somTri[i+1]));
}
else {
suppr(get<1>(somTri[i]),get<1>(somTri[i+1]));
}
if (get<0>(somTri[i])!=get<0>(somTri[i+2]) and nbImpair>0) {
cout<<get<0>(somTri[i])<<endl;
return 0;
}
}
cout<<maxX<<endl;
return 0;
}
if (maxX<=1000 and maxY<=1000) {
for (int i=0;i<nbPoints;i++) {
points[i].first++;
points[i].second++;
}
xMin++;
yMin++;
maxX++;
maxY++;
for (int i=1;i<nbPoints;i++) {
if (points[i-1].first!=points[i].first) {
cumu[points[i-1].first][1]++;
cumu[points[i].first][1]--;
cumu[points[i-1].first][points[i-1].second]--;
cumu[points[i].first][points[i].second]++;
}
}
for (int y=1;y<=maxY;y++) {
for (int x=1;x<=maxX;x++) {
cumu[x][y]+=cumu[x-1][y]+cumu[x][y-1]-cumu[x-1][y-1];
}
}
/*for (int y=maxY;y>0;y--) {
for (int x=1;x<=maxX;x++) {
cout<<cumu[x][y];
}
cout<<endl;
}*/
for (int x=1;x<=maxX;x++) {
for (int y=1;y<=maxY;y++) {
if (cumu[x][y]==1) {
if (cumu[x+1][y]==1 and cumu[x][y+1]==1 and cumu[x+1][y+1]==1) {
emboite[x]=1;
cumu[x][y]=0;
cumu[x+1][y]=0;
cumu[x][y+1]=0;
cumu[x+1][y+1]=0;
//cout<<x<<" "<<y<<endl;
}
else {
for (int z=x-1;z>=0;z--) {
if (emboite[z]==0) {
cout<<z<<endl;
return 0;
}
}
}
}
}
}
cout<<maxX-1<<endl;
return 0;
}
int rep=maxX;
for (int i=1;i<nbPoints;i++) {
if (points[i].second%2!=yMin%2) {
rep=min(rep,points[i-1].first);
}
if (points[i].first%2!=xMin%2) {
rep=min(rep,points[i].first-1);
}
}
cout<<rep<<endl;
/*if (points[0].second%2==points[2].second%2) {
if (points[0].first%2==points[2].first%2) {
cout<<points[2].first<<endl;
}
else {
cout<<points[2].first-1<<endl;
}
}
else {
cout<<xMin<<endl;
}*/
return 0;
}
