#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
struct node
{
int sum,mnpref,mxpref,cnt,st,ed,fa,fb;
};
int valx[MAXN],valy[MAXN],X[MAXN],Y[MAXN],fen[MAXN],f[MAXN];
vector< pair<int,int> > vv[MAXN],vi[MAXN],undo;
node seg[MAXN*4];
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
node merge(node a,node b)
{
node c;
c.sum=a.sum+b.sum;
c.mxpref=max(a.mxpref,a.sum+b.mxpref);
c.mnpref=min(a.mnpref,a.sum+b.mnpref);
c.cnt=a.cnt+b.cnt;
if(a.cnt==0) c.st=b.st;
else c.st=a.st;
if(b.cnt==0) c.ed=a.ed;
else c.ed=b.ed;
if(a.cnt==0) c.fa=b.fa,c.fb=b.fb;
else if(b.cnt==0) c.fa=a.fa,c.fb=a.fb;
else
{
if(a.cnt&1) c.fa=a.fa+b.fb+(a.ed%2!=b.st%2),c.fb=a.fb+b.fa;
else c.fa=a.fa+b.fa,c.fb=a.fb+b.fb+(a.ed%2!=b.st%2);
}
return c;
}
bool check(node a)
{
return (a.sum==0&&a.mnpref==0&&a.mxpref<2&&a.cnt%2==0&&a.fa==0);
}
bool checklegit(node a)
{
return (a.sum==0&&a.mnpref==0&&a.mxpref==0&&a.cnt%2==0&&a.fa==0);
}
void update(int l,int r,int i,int val,int he,int pos)
{
if(i<l||r<i) return ;
if(l==r)
{
if(seg[pos].sum+he) seg[pos]={seg[pos].sum+he,seg[pos].mnpref+he,seg[pos].mxpref+he,1,val,val,0,0};
else seg[pos]={seg[pos].sum+he,seg[pos].mnpref+he,seg[pos].mxpref+he,0,0,0,0,0};
return ;
}
int mid=(l+r)/2;
update(l,mid,i,val,he,pos*2);
update(mid+1,r,i,val,he,pos*2+1);
seg[pos]=merge(seg[pos*2],seg[pos*2+1]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>X[i]>>Y[i];
valx[i]=X[i],valy[i]=Y[i];
}
sort(valx+1,valx+n+1);
sort(valy+1,valy+n+1);
int m=0;
valx[0]=-1;
for(int i=1;i<=n;i++) if(valx[i]!=valx[m]) valx[++m]=valx[i];
for(int i=1;i<=n;i++)
{
X[i]=lower_bound(valx+1,valx+m+1,X[i])-valx;
Y[i]=lower_bound(valy+1,valy+n+1,Y[i])-valy;
}
for(int i=1;i<=n;i++) if(Y[i]==Y[i%n+1])
{
int a=X[i],b=X[i%n+1];
if(a>b) swap(a,b);
vv[a].push_back({Y[i],1}),vv[b].push_back({Y[i],-1});
}
for(int i=1;i<=m;i++)
{
sort(vv[i].begin(),vv[i].end());
for(auto v:vv[i])
{
update(v.first,n,v.second);
if(v.second==1)
{
if(get(v.first)&1) vi[i].push_back({v.first,f[v.first]=1});
else vi[i].push_back({v.first,f[v.first]=-1});
}
else vi[i].push_back({v.first,-f[v.first]});
}
}
for(int i=1;i<=n;i++) f[i]=0;
int ans=0,mx=k;
vector< pair<int,int> > it;
for(int i=1;i<m;i++)
{
int res=valx[i]+valx[i]%2;
if(valx[i]&1) for(auto v:vi[i]) update(1,n,v.first,valy[v.first],v.second,1);
if(!check(seg[1]))
{
mx=min(mx,res);
break;
}
if(checklegit(seg[1])) it.push_back({res,valx[i+1]});
}
for(int i=1;i<=n*4;i++) seg[i]={0,0,0,0,0,0,0,0};
for(int i=1;i<m;i++)
{
int res=valx[i]+1-valx[i]%2;
if(!(valx[i]&1)) for(auto v:vi[i]) update(1,n,v.first,valy[v.first],v.second,1);
if(!check(seg[1]))
{
mx=min(mx,res);
break;
}
if(checklegit(seg[1])) it.push_back({res,valx[i+1]});
}
for(auto v:it) if(v.first<=mx) ans=max(ans,v.first+(min(v.second,mx)-v.first)/2*2);
cout<<ans;
}
