#include <bits/stdc++.h>
using namespace std;
struct segTree{
struct node{
///vertical range:
int len;
int prefcnt, sufcnt; ///stores current active count
bool oddrang; ///stores if odd rang has been discovered
///horizontal range:
bool oddtim; ///stores if odd start x exists.
bool evtim; ///stores if even start x exists.
///lazy:
bool lazodd; ///stores if range was changed to this
bool lazev; ///stores if range was changed to this
bool delted; ///stores if has been deleted
///no need to store for vertical since length is predetermined
///if lazodd||lazev, range was updated to be active
///must ensure both lazev and lazodd are not one at same time in push
///childs:
int l,r;
};
node unite(node a, node b){
node ans;
ans=def;
ans.len=a.len+b.len;
ans.prefcnt = a.prefcnt + (a.prefcnt==a.len ? b.prefcnt : 0);
ans.sufcnt = b.sufcnt + (b.sufcnt == b.len ? a.sufcnt : 0);
ans.oddrang = a.oddrang||b.oddrang||(((a.sufcnt+b.prefcnt)%2)&&(ans.prefcnt==0)&&(ans.sufcnt==0));
ans.oddtim=a.oddtim||b.oddtim;
ans.evtim=a.evtim||b.evtim;
assert(!(a.lazodd||b.lazodd||a.lazev||b.lazev||a.delted||b.delted));
return ans;
}
int cr = 0;
void makeKids(int l, int r, int ind){
if(l==r)
return;
if(st[ind].l!=-1)
return;
int mid = (l+r)/2;
st[ind].l=++cr;
st[st[ind].l].len=(mid-l+1);
st[ind].r=++cr;
st[st[ind].r].len=(r-mid);
}
void push(int l, int r, int ind){
makeKids(l,r,ind);
if(st[ind].lazodd||st[ind].lazev){
///this was activated
assert(!st[ind].delted);
assert(st[ind].lazodd^st[ind].lazev);
if(st[ind].lazodd){
st[ind].evtim=0;
st[ind].oddtim=1;
st[ind].prefcnt=st[ind].len;
st[ind].sufcnt=st[ind].len;
st[ind].oddrang=0;
if(l<r){
st[st[ind].l].lazodd=1;
st[st[ind].l].lazev=0;
st[st[ind].l].delted=0;
st[st[ind].r].lazodd=1;
st[st[ind].r].lazev=0;
st[st[ind].r].delted=0;
}
st[ind].lazodd=0;
}
else{
st[ind].evtim=1;
st[ind].oddtim=0;
st[ind].prefcnt=st[ind].len;
st[ind].sufcnt=st[ind].len;
st[ind].oddrang=0;
if(l<r){
st[st[ind].l].lazodd=0;
st[st[ind].l].lazev=1;
st[st[ind].l].delted=0;
st[st[ind].r].lazodd=0;
st[st[ind].r].lazev=1;
st[st[ind].r].delted=0;
}
st[ind].lazev=0;
}
}
else if(st[ind].delted){
///was deleted pass on
st[ind]=def;
st[ind].len=r-l+1;
if(l<r){
st[st[ind].l].delted=1;
st[st[ind].l].lazodd=st[st[ind].l].lazev=0;
st[st[ind].r].delted=1;
st[st[ind].r].lazodd=st[st[ind].r].lazev=0;
}
st[ind].delted=0;
}
}
node *st;
node def;
segTree(int nodes){
st=new node[nodes];
def.prefcnt=0;
def.len=0;
def.sufcnt=0;
def.oddrang=0;
def.oddtim=0;
def.evtim=0;
def.lazodd=0;
def.lazev=0;
def.delted=0;
def.l=-1;
def.r=-1;
fill(st,st+nodes,def);
}
void flip(int l, int r, int s, int e, int ind, int tim){
push(l,r,ind);
if(e<l||s>r){
return;
}
if(s<=l&&r<=e){
///figure out if exists or no
if(st[ind].oddtim||st[ind].evtim){
///it has been removed
st[ind].delted=1;
push(l,r,ind);
}
else{
///has come into existance
if(tim%2){
st[ind].lazodd=1;
}
else{
st[ind].lazev=1;
}
push(l,r,ind);
}
return;
}
int mid = (l+r)/2;
flip(l,mid,s,e,st[ind].l,tim);
flip(mid+1,r,s,e,st[ind].r,tim);
int lef = st[ind].l;
int rig = st[ind].r;
st[ind]=unite(st[st[ind].l],st[st[ind].r]);
st[ind].l=lef;
st[ind].r=rig;
}
node query(int l, int r, int s, int e, int ind){
push(l,r,ind);
if(e<l||s>r){
return def;
}
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
node ans = unite(query(l,mid,s,e,st[ind].l),query(mid+1,r,s,e,st[ind].r));
return ans;
}
};
const int mxy = 1e9+5;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
int lasx,lasy;
cin >> lasx >> lasy;
int firx = lasx;
int firy = lasy;
lasy++;
map<int,vector<array<int,2>>>mp;
for(int i = 1;i<n;i++){
int x,y;
cin >> x >> y;
y++;
if(x==lasx){
mp[x].push_back({min(lasy,y),max(lasy,y)});
}
lasx=x;
lasy=y;
}
firy++;
if(firx==lasx){
mp[firx].push_back({min(lasy,firy),max(lasy,firy)});
}
///sorted evs on x
segTree st(1e7);
int ans = 0;
for(pair<int,vector<array<int,2>>>p:mp){
int x = p.first;
///check this x
if((st.st[0].oddtim&&(x%2==0))||((st.st[0].evtim&&(x%2==1)))){
///bad
}
else{
///x is possible
ans=max(ans,x);
}
///check x-1
x--;
if((st.st[0].oddtim&&(x%2==0))||((st.st[0].evtim&&(x%2==1)))){
///bad
}
else{
///x is possible
ans=max(ans,x);
}
x++;
///do updates on x
bool val = 1;
for(array<int,2>upd : p.second){
upd[1]--;
segTree::node cur = st.query(0,mxy,upd[0],upd[1],0);
if((cur.oddtim&&(x%2==0))||(cur.evtim&&(x%2==1))){
val=0;
break;
}
st.flip(0,mxy,upd[0],upd[1],0,x);
}
if(!val||st.st[0].oddrang)
break;
}
cout << ans;
return 0;
}
