#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define SN 1200000
using namespace std;
struct reads
{
	long long num;
	int data;
	bool operator < (const reads &t)const
	{
		return num<t.num;	
	}
};
reads st[SN+1],tong[SN+1];
struct seg
{
	struct node
	{
		int l,r;
		long long maxn,lazy;
	};
	node tree[(SN<<2)+1];
	void push_up(int k)
	{
		tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1|1].maxn);
		return;
	}
	void spread(int k)
	{
		if (tree[k].lazy)
		{
			tree[k<<1].maxn+=tree[k].lazy,tree[k<<1].lazy+=tree[k].lazy;
			tree[k<<1|1].maxn+=tree[k].lazy,tree[k<<1|1].lazy+=tree[k].lazy;
			tree[k].lazy=0;
		}
		return;
	}
	void build(int k,int l,int r)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r);
		return;
	}
	void get_maxn(int k,int x,long long d)
	{
		if (tree[k].l==tree[k].r)
		{
			tree[k].maxn=max(tree[k].maxn,d);
			return;
		}
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (x<=mid) get_maxn(k<<1,x,d);
		else get_maxn(k<<1|1,x,d);
		push_up(k);
		return;
	}
	void add(int k,int l,int r,int d)
	{
		if (l>r) return;
		if (tree[k].l==l&&tree[k].r==r)
		{
			tree[k].maxn+=d,tree[k].lazy+=d;
			return;
		}
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) add(k<<1,l,r,d);
		else if (l>=mid+1) add(k<<1|1,l,r,d);
		else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
		push_up(k);
		return;
	}
};
seg T;
int n,length,leng,top,lg[SN+1];
long long k,dque[SN+1],delta[SN+1];
vector<reads>v[SN+1];
void adder(long long l,long long r,int d)
{
	if (l/k==r/k)
	{
		int sl=lower_bound(dque+1,dque+top+1,l%k)-dque,sr=lower_bound(dque+1,dque+top+1,r%k+1)-dque-1;
		T.add(1,sl,sr,d);
	}
	else if (l/k!=r/k)
	{
		int sl=lower_bound(dque+1,dque+top+1,l%k)-dque,sr=lower_bound(dque+1,dque+top+1,r%k+1)-dque-1;
		T.add(1,sl,top,d),T.add(1,1,sr,d),T.add(1,1,top,d*(r/k-l/k-1));
	}
	return;
}
long long play_game(long long N,int Q,long long K,vector<long long>L,vector<long long>R)
{
	long long ps,res=0,d,pst=0,ans=0;
	for (int i=2;i<=SN;++i) lg[i]=lg[i>>1]+1;
	n=N,k=K;
	for (int i=0;i<Q;++i) tong[++length]=(reads){L[i],1},tong[++length]=(reads){R[i]+1,-1};
	sort(tong+1,tong+length+1);
	for (int i=1;i<=length;++i)
	{
		res+=tong[i].data;
		if (i!=length&&tong[i].num!=tong[i+1].num)
		{
			d=tong[i+1].num-tong[i].num;
			if (d>=(k<<1)) ans+=((d-k)/k)*res,d-=((d-k)/k)*k;
			++leng,st[leng].num=st[leng-1].num+d,st[leng].data=res;
		}
	}
	dque[++top]=0,dque[++top]=1,dque[++top]=k;
	for (int i=1;i<=leng;++i) dque[++top]=st[i].num%k+1,dque[++top]=(st[i-1].num+1)%k+1;
	for (int i=1;i<=leng;++i)
		if (st[i-1].num+1-k>=1)
		{
			ps=0;
			for (int j=lg[leng];j>=0;--j)
				if (ps+(1<<j)<=leng&&st[ps+(1<<j)-1].num+1<=st[i-1].num+1-k)
					ps+=(1<<j);
			v[ps].push_back((reads){st[i-1].num+1-k,i});
		}
	sort(dque+1,dque+top+1),top=unique(dque+1,dque+top+1)-dque-1,T.build(1,1,top);
	for (int i=1;i<=leng;++i)
	{
		T.get_maxn(1,lower_bound(dque+1,dque+top+1,(st[i-1].num+1)%k)-dque,delta[i]),pst=st[i-1].num;
		for (int j=0;j<v[i].size();++j)
		{
			if (pst+1<=v[i][j].num) adder(pst+1,v[i][j].num,st[i].data);
			delta[v[i][j].data]=T.tree[1].maxn,pst=v[i][j].num;
		}
		if (pst+1<=st[i].num) adder(pst+1,st[i].num,st[i].data);
	}
	return ans+T.tree[1].maxn;
}