#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l+r)/2)
#define db double
const int N=2e5+5,M=1e7+5,up=1e9;
int n,m,tp,ans,cnt[4],x[N],y[N];struct Event {int tim,l,r;}a[N];
int rt,cntS;struct Seg {int vl,ch[2];bool tg;}sg[N*4];
struct Node {int tim,l,r,vl,vl1;};
bool operator < (Node x,Node y) {return x.r<y.r;};set<Node> z;
void fail() {printf("%d\n",ans);exit(0);}
int f(int x,int y) {if(x==-1) return y;if(y==-1) return x;if(x!=y) fail();return x;}
void pu(int p) {sg[p].vl=sg[sg[p].ch[0]].vl+sg[sg[p].ch[1]].vl;}
void mdf(int p,int l,int r) {sg[p].vl=r-l-sg[p].vl+1;sg[p].tg^=1;}
void pd(int p,int l,int r)
{
    if(!sg[p].ch[0]) sg[p].ch[0]=++cntS;if(!sg[p].ch[1]) sg[p].ch[1]=++cntS;
    if(sg[p].tg) mdf(sg[p].ch[0],l,mid),mdf(sg[p].ch[1],mid+1,r),sg[p].tg=0;
}
void upd(int &p,int l,int r,int qL,int qR)
{
   if(l>qR || r<qL) return; if(!p) p=++cntS;
   if(l>=qL && r<=qR) {mdf(p,l,r);return;}pd(p,l,r);
    upd(sg[p].ch[0],l,mid,qL,qR);upd(sg[p].ch[1],mid+1,r,qL,qR);pu(p);
}
int qry(int p,int l,int r,int qL,int qR)
{
    if(l>qR || r<qL || !p) return 0;
    if(l>=qL && r<=qR) return sg[p].vl;pd(p,l,r);
    return qry(sg[p].ch[0],l,mid,qL,qR)+qry(sg[p].ch[1],mid+1,r,qL,qR);
}
void upd1(Node &x,int vl)
{
    if(x.vl1==-1)
    {
         if(x.r-x.l&1) x.vl1=3;else if(x.vl==-1) x.vl1=x.tim&1;
        else if((x.l^x.vl)&1) x.vl1=3;
        else if(qry(rt,0,up,x.l,x.r-1)==x.r-x.l) x.vl1=(x.tim&1)^1;
        else x.vl1=2;
    }cnt[x.vl1]+=vl;
}
void upd2(int tim,Node &x)
{
    if(tim-x.tim&1) upd(rt,0,up,x.l,x.r-1);
    if(x.vl==-1) x.vl=x.l&1;if(!qry(rt,0,up,x.l,x.r-1)) x.vl=-1;
}
void ins(int tim,int l,int r)
{
    // printf("ins %d %d %d\n",tim,l,r);
    Node t=(Node) {tim,l,r,-1,-1};auto it=z.lower_bound(t);
    if(it!=z.end() && l>=it->l && r<=it->r)
    {
        Node t1=*it;upd1(t1,-1);upd2(tim,t1);z.erase(it);
        if(qry(rt,0,up,l,r-1)) fail();t.vl=t1.vl;
        t.l=t1.l;t.r=l;t.vl=t1.vl;
        if(t.l<t.r) {if(!qry(rt,0,up,t.l,t.r)) t.vl=-1;z.insert(t);upd1(t,1);}
        t.l=r;t.r=t1.r;t.vl=t1.vl;
        if(t.l<t.r) {if(!qry(rt,0,up,t.l,t.r)) t.vl=-1;z.insert(t);upd1(t,1);}
        return;
    }
    if(it!=z.end() && r==it->l)
    {
        Node t1=*it;upd1(t1,-1);upd2(tim,t1);z.erase(it);
        t.r=t1.r;t.vl=f(t.vl,t1.vl);
    }
    it=z.lower_bound(t);
    if(it!=z.begin() && l==(it=prev(it))->r)
    {
        Node t1=*it;upd1(t1,-1);upd2(tim,t1);z.erase(it);
        t.l=t1.l;t.vl=f(t.vl,t1.vl);
    }if(t.l<t.r) upd1(t,1),z.insert(t);
}
int main()
{
    scanf("%d %d",&n,&m);for(int i=1;i<=n;++i) scanf("%d %d",&x[i],&y[i]);
    x[n+1]=x[1];y[n+1]=y[1];
    for(int i=1;i<=n;++i) if(x[i]==x[i+1])
        a[++tp]=(Event) {x[i],min(y[i],y[i+1]),max(y[i],y[i+1])};
    sort(a+1,a+tp+1,[](Event x,Event y) {return x.tim<y.tim;});
    for(int i=1;i<tp;++i)
    {
        ins(a[i].tim,a[i].l,a[i].r);
        // printf("z=");
        // for(auto j:z) printf("(%d %d %d %d)",j.tim,j.l,j.r,j.vl);putchar('\n');
        if(a[i].tim!=a[i+1].tim)
        {
            // printf("cnt=%d %d %d %d\n",cnt[0],cnt[1],cnt[2],cnt[3]);
            if(cnt[3]) fail();
            if(!cnt[2])
            {
                if(!cnt[0]) ans=max(ans,a[i+1].tim-(!(a[i+1].tim&1)));
                if(!cnt[1]) ans=max(ans,a[i+1].tim-(a[i+1].tim&1));
            }
        }
    }fail();return 0;
}