#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 int val(reg int x){return vis[*s.lower_bound(x)];}
inline bool chk(reg int x,reg int i){return val(x)==i;}
inline void upd(reg int x,reg int k){vis[x]>-1?cnt[vis[x]]+=k:0;}
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)),vis[0]=1e9;
	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;
	}
	by[0]=-1,by[my+1]=2e9,s.insert(0),s.insert(my+1);
	for (reg int i=1;i<=mx;i++){
		reg int len=0,flg=0;
		// std::cerr<<"ans "<<cnt[0]<<" "<<cnt[1]<<"\n";
		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]){

		// for (auto it:s) std::cerr<<by[it]<<" "; std::cerr<<"\n";
		// std::cerr<<by[l]<<" "<<by[r]<<"\n";	
		// std::cerr<<by[l]<<" "<<vis[l]<<"\n";

			reg int ty=val(r)>-1; 
			vis[l]=val(l),vis[r]=val(r),s.insert(l),s.insert(r),upd(l,1),upd(r,1);
			auto L=s.upper_bound(l),R=s.upper_bound(r);
			// std::cerr<<"<< "<<by[*L]<<" "<<by[*R]<<"\n";
			if (ty){
				for (auto it=L;it!=R;++it) if ((bx[i]&1)!=vis[*it]){flg=1;break;}
			}
			if (by[r]-by[l]&1){ 
				// std::cerr<<"<< "<<vis[*s.lower_bound(l)]<<" "<<(bx[i]&1)<<"\n";
				if (!chk(l,bx[i]&1)&&!chk(r+1,bx[i]&1)){flg=1;break;} 
			}
			// std::cerr<<"last "<<vis[l]<<"\n";
			for (auto it=L;it!=R;++it){
				if (ty) upd(*it,-1); 
				vis[*it]=ty?-1:bx[i]&1;
			}
			// std::cerr<<"<< "<<vis[l]<<" "<<l<<" "<<r<<"\n";
			s.erase(L,R),vis[r]=ty?-1:bx[i]&1,vis[r]>-1?cnt[vis[r]]++:0,s.insert(r);
			if (val(l)==val(*--s.lower_bound(l))) 
				s.erase(--s.lower_bound(l)),upd(l,-1);
			if (val(r)==val(*--s.lower_bound(r))) 
				s.erase(--s.lower_bound(r)),upd(r,-1);
			if (val(*s.upper_bound(r))==val(*--s.upper_bound(r))) 
				s.erase(--s.upper_bound(r)),upd(*s.upper_bound(r),-1);
			
			// if (vis[*R]!=(ty?-1:bx[i]&1)){
			// 	// std::cerr<<"appear\n";
			// 	vis[r]=(ty?-1:bx[i]&1),s.insert(r);
			// 	if (vis[r]>-1) cnt[vis[r]]++;
			// }

			// if (vis[l]!=val(r)) vis[l]>-1?cnt[vis[l]]++:0,s.insert(l); 
			// else vis[l]>-1?cnt[vis[l]]--:0,s.erase(l); 
		}
		if (flg) break; 
		
		// for (auto it:s) if (by[it]&1) std::cerr<<by[it]<<" "; std::cerr<<"\n";
		// std::cerr<<i<<" "<<"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;}
		// 	_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;}
		// 	_it=it,++_it; if (vis[*_it]!=-1&&(by[*_it]-by[*it]&1)){flg=1;break;}
		// 	// std::cerr<<"<< "<<*it<<" "<<*_it<<"\n";
		// }
		for (auto it=++s.begin();it!=s.end();it++){
			auto lst=it; --lst; if (vis[*it]<0||by[*lst]<0) continue;
			assert(vis[*it]!=vis[*lst]);
			if ((by[*it]-by[*lst])&1){
				std::cerr<<by[*it]<<" "<<by[*lst]<<"\n";
				flg=1;break;
			}
		}
		if (flg) break;	
		std::cerr<<"right "<<i<<"\n";
	}
	printf("%d\n",ans);
	return 0;
}