#include<bits/stdc++.h>
#define reg register
#define int long long
inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
inline int max(reg int x,reg int y){return x>y?x:y;}
inline int min(reg int x,reg int y){return x<y?x:y;}
const int N=1e6+10,INF=4e18;
int n,q,K,b[N],B[N],tot,m,sum[N];
int mx[N<<2],tag[N<<2];
inline void pushup(reg int o){mx[o]=max(mx[o<<1],mx[o<<1|1]);}
inline void brush(reg int o,reg int k){mx[o]+=k,tag[o]+=k;}
inline void pushdown(reg int o){if (tag[o]) brush(o<<1,tag[o]),brush(o<<1|1,tag[o]),tag[o]=0;}
void build(reg int o,reg int l,reg int r){
    if (l==r) return mx[o]=l==1?0:-INF,void(); reg int mid=l+r>>1; 
    build(o<<1,l,mid),build(o<<1|1,mid+1,r),pushup(o);
}
void modify(reg int o,reg int l,reg int r,reg int L,reg int R,reg int k){
    if (L>R) return; if (L<=l&&r<=R) return brush(o,k); reg int mid=l+r>>1; pushdown(o);
    if (L<=mid) modify(o<<1,l,mid,L,R,k); if (R>mid) modify(o<<1|1,mid+1,r,L,R,k); pushup(o);
}
int query(reg int o,reg int l,reg int r,reg int L,reg int R){
    if (L>R) return 0; if (L<=l&&r<=R) return mx[o]; reg int mid=l+r>>1,res=0; pushdown(o);
    if (L<=mid) cmax(res,query(o<<1,l,mid,L,R)); if (R>mid) cmax(res,query(o<<1|1,mid+1,r,L,R)); return res;
}
void update(reg int o,reg int l,reg int r,reg int x,reg int k){
    if (l==r) return cmax(mx[o],k),void(); reg int mid=l+r>>1; pushdown(o);
    x<=mid?update(o<<1,l,mid,x,k):update(o<<1|1,mid+1,r,x,k); pushup(o);
}
inline int get(reg int x){
    reg int p=std::lower_bound(B+1,B+tot+1,x)-B;
    assert(x==B[p]); return p;
}
#undef int 
long long play_game(long long _N, int _Q, long long _K, std::vector<long long> _L, std::vector<long long> _R){
    #define int long long
    n=_N,q=_Q,K=_K; 
    B[++tot]=-1,B[++tot]=0,B[++tot]=K-1;
    for (reg int i=0;i<q;i++){
        b[++m]=_L[i],b[++m]=_R[i]+1;
        B[++tot]=_L[i]%K,B[++tot]=(_R[i]+1)%K;
    }
    std::sort(b+1,b+m+1),m=std::unique(b+1,b+m+1)-b-1;
    std::sort(B+1,B+tot+1),tot=std::unique(B+1,B+tot+1)-B-1;
    build(1,1,tot);
    for (reg int i=0;i<q;i++) sum[std::lower_bound(b+1,b+m+1,_L[i])-b]++,sum[std::lower_bound(b+1,b+m+1,_R[i]+1)-b]--;
    for (reg int i=1;i<=m;i++) sum[i]+=sum[i-1];
    for (reg int i=1,lst=-1,j;i<=m;i=j){
        reg int nw=b[i]/K;
        for (j=i;j<=m&&nw==b[j]/K;) j++;
        if (nw-lst>1){
            update(1,1,tot,1,mx[1]+sum[i-1]*(nw-lst-2));
            modify(1,1,tot,2,tot,sum[i-1]*(nw-lst-1));
        }
        reg int Mx=mx[1],L=0; std::vector<std::tuple<int,int,int>> vc;
        for (reg int x=i;x<j;x++) 
            update(1,1,tot,get(b[x]%K),query(1,1,tot,1,get(b[x]%K))),
            vc.push_back({get(L),get(b[x]%K)-1,sum[x-1]}),L=b[x]%K;
        vc.push_back({get(L),get(K-1),sum[j-1]}),update(1,1,tot,1,Mx);
        for (auto [l,r,x]:vc) modify(1,1,tot,l,r,x); lst=nw;
    }
    return mx[1];
}