首先有一个显然的 $\mathcal O(n)$ DP，$f_i=\max\{f_{i-1},f_{i-k}+a_{i-k}\}$。

可以将 $f$ 每 $k$ 个分一层，编号 $0\sim k-1$，那么就是两层相同位置转移或者前后转移。

由于 $a$ 是由 $q$ 次区间 $+1$ 得到的，那么颜色段一定在 $\mathcal O(q)$ 及以内。考虑每个颜色段怎么做。

对于同一层的 $a$ 在相同颜色段的情况：设 $f,g$ 为相邻的两层，那么 $g_i=\max\{f_i+a,g_{i-1}\}$。发现存在分界点使得分界点及以前 $g_i=g_{i-1}$，分界点以后 $g_i=f_i+a$。

:::info[证明]{open} 显然地，$f$ 单调递增，则 $f_i\le f_{i+1}$。

假设 $g_i=f_i+a$，那么 $g_i\le f_{i+1}+a$。

即如果存在 $i$ 使得 $g_i=f_i+a$，那么对于所有 $j>i$，都有 $g_j=f_j+a$。 :::

这样可以把一个颜色段按层分割成 $\mathcal O(\frac{n}{k})$段，一轮转移就是区间赋值和区间加，线段树维护，找分割点可以线段树二分。

但是 $k$ 较小时开销太大。每个颜色段的第一层、最后一层和第二完整层（如果有），它们 $a$ 相同因此可以像上面那样转移。对于第三层到倒数第二层，我们发现贪心选择 $f_i=f_{i-k}+a$ 一定不劣，线段树区间加若干次 $a$ 即可。

:::success[AC 代码]{open}

#include <bits/stdc++.h>
#define fi first
#define se second
#define mid ((l+r)>>1)
#define bmid ((l+r+1)>>1)
#define pb push_back
#define eb emplace_back
using namespace std;
using ll= long long;
#ifndef ONLINE_JUDGE
template <typename tp>
void _debug(const tp& t) {cerr<<t<<'\n';}
template <typename tp,typename... args>
void _debug(const tp& t, const args&... rest) {cerr<<t<<' ';_debug(rest...);}
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)
#else
#define debug(...) 0
#endif
#define inf 1000000000000000000ll
const int N=250005,H=60000000,mod=1000000007;
ll val[H],hht[H],lfy[H];
int root,tot,lc[H],rc[H];
void add(int& u,ll x) {
	if(!u) u=++tot,hht[u]=-1;
	val[u]+=x;
	if(~hht[u]) hht[u]+=x;
	else lfy[u]+=x;
}
void fuz(int& u,ll x) {
	if(!u) u=++tot,hht[u]=-1;
	val[u]=x,hht[u]=x,lfy[u]=0;
}
void pushdown(int u) {
	if(~hht[u]) {
		fuz(lc[u],hht[u]);
		fuz(rc[u],hht[u]);
		hht[u]=-1;
	}
	if(lfy[u]) {
		add(lc[u],lfy[u]);
		add(rc[u],lfy[u]);
		lfy[u]=0;
	}
}
void pushup(int u) {
	val[u]=max(val[lc[u]],val[rc[u]]);
}
void add(int& u,ll l,ll r,ll s,ll t,ll x) {
	if(!u) u=++tot,hht[u]=-1;
	if(s<=l&&r<=t) return add(u,x);
	pushdown(u);
	if(s<=mid) add(lc[u],l,mid,s,t,x);
	if(t>mid) add(rc[u],mid+1,r,s,t,x);
	pushup(u);
}
void fuz(int& u,ll l,ll r,ll s,ll t,ll x) {
	if(!u) u=++tot,hht[u]=-1;
	if(s<=l&&r<=t) return fuz(u,x);
	pushdown(u);
	if(s<=mid) fuz(lc[u],l,mid,s,t,x);
	if(t>mid) fuz(rc[u],mid+1,r,s,t,x);
	pushup(u);
}
ll ef(int u,ll l,ll r,ll s,ll t,ll x) {
	if(val[u]<x) return -1;
	if(l==r) return l;
	pushdown(u);
	if(s<=l&&r<=t) {
		const ll tm=ef(lc[u],l,mid,s,t,x);
		if(~tm) return tm;
		return ef(rc[u],mid+1,r,s,t,x);
	}
	if(s<=mid) {
		const ll tm=ef(lc[u],l,mid,s,t,x);
		if(~tm) return tm;
	}
	if(t>mid) return ef(rc[u],mid+1,r,s,t,x);
	return -1;
}
ll query(int u,ll l,ll r,ll s) {
	if(l==r||!u) return val[u];
	pushdown(u);
	if(s<=mid) return query(lc[u],l,mid,s);
	return query(rc[u],mid+1,r,s);
}
#define add(l,r,x) add(root,0,k-1,l,r,x)
#define fuz(l,r,x) fuz(root,0,k-1,l,r,x)
#define ef(l,r,x) ef(root,0,k-1,l,r,x)
ll n,k;
void gao(ll l,ll r,ll a) {
	const ll t=ef(l,r,val[root]-a); // val[root] 为最大值，即 f[k-1]，t 是第一个 f[i]+a>=f[k-1]
	if(t==-1) fuz(l,r,val[root]);
	else {
		if(t>l) fuz(l,t-1,val[root]);
		if(a) add(t,r,a);
	}
//	cout<<l<<' '<<r<<": ";for(int i=0;i<k;i++) cout<<query(root,0,k-1,i)<<" \n"[i==k-1];
}
ll play_game(ll nn,signed q,ll kk,vector<ll> lv,vector<ll> rv) { k=kk,n=nn;
	map<ll,int> cf;
	cf[n]=0;
	for(ll& i: lv) cf[i]++;
	for(ll& i: rv) cf[i+1]--;
	vector<pair<ll,int> > vec;
	for(auto i: cf) vec.pb(i);
	ll a=0;
	for(int i=0;i+1<vec.size();i++) {
		a+=vec[i].se;
		ll l=vec[i].fi,r=vec[i+1].fi-1;
		ll hht=l/k,lfy=r/k; l%=k,r%=k;
		if(hht==lfy) { // 颜色段只经过一层
			gao(l,r,a);
			continue;
		}
		gao(l,k-1,a); // 第一层
		if(lfy-hht>1) gao(0,k-1,a); // 第二层
		if(lfy-hht>2) gao(0,k-1,a*(lfy-hht-2)); // 第三层到倒数第二层
		gao(0,r,a); // 最后一层
	}
	return query(root,0,k-1,(n-1)%k);
}
#ifndef ONLINE_JUDGE
signed main() {
//	k=50;
//	add(0,39,1);
//	cout<<ef(40,48,-1);
//	return 0;
	cin.tie(nullptr)->sync_with_stdio(false);
	ll n,k;
	int q;
	cin>>n>>q>>k;
	vector<ll> l(q),r(q);
	for(int i=0;i<q;i++)
		cin>>l[i]>>r[i];
	cout<<play_game(n,q,k,l,r);
	return 0;
}
#endif

:::