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