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