#include <bits/stdc++.h>
using namespace std;
struct segTree{
struct node{
///vertical range:
int len;
int prefoddcnt, sufoddcnt; ///stores current active count
int prefevcnt, sufevcnt; ///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.prefoddcnt = a.prefoddcnt + (a.prefoddcnt==a.len ? b.prefoddcnt : 0);
ans.prefevcnt = a.prefevcnt + (a.prefevcnt==a.len ? b.prefevcnt : 0);
ans.sufoddcnt = b.sufoddcnt + (b.sufoddcnt == b.len ? a.sufoddcnt : 0);
ans.sufevcnt = b.sufevcnt + (b.sufevcnt == b.len ? a.sufevcnt : 0);
ans.oddrang = a.oddrang||b.oddrang||(((a.sufoddcnt+b.prefoddcnt)%2)&&(a.sufoddcnt!=a.len)&&(b.prefoddcnt!=b.len))||(((a.sufevcnt+b.prefevcnt)%2)&&(a.sufevcnt!=a.len)&&(b.prefevcnt!=b.len));
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].prefoddcnt=st[ind].len;
st[ind].prefevcnt=0;
st[ind].sufoddcnt=st[ind].len;
st[ind].sufevcnt=0;
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].prefoddcnt=0;
st[ind].prefevcnt=st[ind].len;
st[ind].sufoddcnt=0;
st[ind].sufevcnt=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
int lef = st[ind].l;
int rig = st[ind].r;
st[ind]=def;
st[ind].l=lef;
st[ind].r=rig;
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.prefoddcnt=0;
def.prefevcnt=0;
def.len=0;
def.sufoddcnt=0;
def.sufevcnt=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(3e7);
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
if(x){
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;
}
