#include<bits/stdc++.h>
// #define int long long
#define reg register
inline int read(){
	int k=1,x=0;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
	return k*x;
}
const int N=5e5+10,INF=1e18;
int n,m,mx,my,bx[N],by[N],ans;
struct Node{int x,y;}p[N];
std::vector<std::pair<int,int>> vc[N];
int vis[N],cnt[2];
std::set<int> s;
inline bool chk(reg int x,reg int i){return vis[x]!=-1&&!(bx[i]-vis[x]&1);}
inline int val(reg int x){return vis[*s.lower_bound(x)];}
signed main(){
	n=read(),m=read();
	for (reg int i=1;i<=n;i++) bx[++mx]=p[i].x=read(),by[++my]=p[i].y=read(); 
	std::sort(bx+1,bx+mx+1),std::sort(by+1,by+my+1);
	mx=std::unique(bx+1,bx+mx+1)-bx-1,my=std::unique(by+1,by+my+1)-by-1;
	for (reg int i=1;i<=n;i++){
		p[i].x=std::lower_bound(bx+1,bx+mx+1,p[i].x)-bx;
		p[i].y=std::lower_bound(by+1,by+my+1,p[i].y)-by;
	}
	p[n+1]=p[1];
	for (reg int i=1;i<=n;i++) if (p[i].x==p[i+1].x)
		vc[p[i].x].push_back({std::min(p[i].y,p[i+1].y),std::max(p[i].y,p[i+1].y)});
	memset(vis,-1,sizeof(vis));
	for (reg int i=1;i<=mx;i++){
		std::vector<std::pair<int,int>> vec;
		std::sort(vc[i].begin(),vc[i].end());
		for (auto [l,r]:vc[i]) 
			if (vec.empty()||vec.back().second!=l) vec.push_back({l,r}); 
			else vec.back().second=r; 
		vc[i]=vec;
	}
	bx[0]=-1,s.insert(0),s.insert(my+1);
	for (reg int i=1;i<=mx;i++){
		reg int len=0,flg=0;
		if (!cnt[0]||!cnt[1]){
			if (cnt[0]) ans=bx[i]&1?bx[i]-1:bx[i];
			if (cnt[1]) ans=bx[i]&1?bx[i]:bx[i]-1;
		}
		for (auto [l,r]:vc[i]){
			reg int ty=val(r)>-1;
			auto L=s.upper_bound(l),R=s.upper_bound(r);
			if (ty) for (auto it=L;it!=R;++it) if ((bx[i]&1)!=vis[*it]){flg=1;break;}
			if (by[r]-by[l]&1){ if (!chk(l,bx[i]&1)&&!chk(r+1,bx[i]&1)){flg=1;break;} }
			if (L!=s.end()) vis[l]=vis[*L]; 
			for (auto it=L;it!=R;++it){
				if (ty) cnt[vis[*it]]--; 
				vis[*it]=ty?-1:bx[i]&1;
			}
			s.erase(L,R);
			if (vis[l]!=(bx[i]&1)) vis[l]>0?cnt[vis[l]]++:0,s.insert(l);
			if (R!=s.end()&&vis[*R]!=(bx[i]&1)) cnt[vis[r]=bx[i]&1]++,s.insert(r);
		}
		if (flg) break; 
		// for (auto it:s) std::cerr<<it<<" "; std::cerr<<"\n";
		// std::cerr<<"qwq\n";
		for (auto [l,r]:vc[i]){
			auto it=s.lower_bound(l),_it=it; --_it;
			if (vis[*it]!=-1&&(by[*it]-by[*_it]&1)){flg=1;break;}
			
			// std::cerr<<"<< "<<*it<<" "<<*_it<<"\n";

			it=s.lower_bound(r); _it=it,--_it;

			if (vis[*it]!=-1&&(by[*it]-by[*_it]&1)){flg=1;break;}
		
			// std::cerr<<"<< "<<*it<<" "<<*_it<<"\n";
		}
		if (flg) break;	
		// std::cerr<<"right "<<i<<"\n";
	}
	printf("%d\n",ans);
	return 0;
}