#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];
inline void upd(reg int i){
	reg int op=-1,flg=0;
	for (reg int j=2;j<=my;j++) if (vis[j]>-1){
		reg int d=bx[i]-bx[vis[j]]&1;
		if (op==-1) op=d; else if (op!=d){flg=1;break;}
	}
	if (!flg) ans=bx[i]-op,std::cerr<<bx[i]-op<<"\n";
}
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+mx+1,p[i].y)-by;
	}
	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)});
	for (reg int i=1;i<=mx;i++){
		upd(i);
		reg int flg=0;
		for (auto [l,r]:vc[i]){
			// if (i==3) std::cerr<<l<<" "<<r<<"\n";
			for (reg int j=l+1;j<=r;j++){ 
				if (vis[j]>-1&&(bx[i]-bx[vis[j]]&1)){flg=1;break;}
				vis[j]=vis[j]?-1:i;
			}	
		}
		if (flg) break;
		reg int len=0;
		for (reg int j=2;j<=my;j++) 
			if (vis[j]==-1){if (len&1){flg=1;break;} len=0;}  
			else len+=by[j]-by[j-1];
		if (flg&&(len&1)) break;
	}
	printf("%d\n",ans);
	return 0;
}