#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INFINI=1000*1000*1000+5,TAILLE_MAX=200*1000+5,COORD_MAX=1000+5;
int nbPoints,maxX;
pair<int,int> initPoint[TAILLE_MAX];
pair<int,int> points[TAILLE_MAX];
int cumu[COORD_MAX][COORD_MAX];
int emboite[TAILLE_MAX];
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;
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);
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 (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;
}
