考虑枚举其中一个区间取 \([i, i + K - 1]\)，考虑对于每个 \(j\) 一次性处理出，区间取 \([j - K + 1, j]\) 多产生的贡献（即以 \(j\) 为右端点）。
对于一个 \([l_k, r_k]\)，设其与 \([i, i + K - 1]\) 的交长度为 \(t\)。如果 \(t = \min(r_k - l_k + 1, K)\) 则显然不会多产生贡献，直接判掉。否则：
-
若 \(r_k - l_k + 1 \ge K\)，当 \(j\) 取 \([l_k + t, l_k + K - 1]\) 时，产生的贡献分别为 \(1, 2, \ldots, K - t\)；当 \(j\) 取 \([l_k + K, r_k]\) 时，产生的贡献均为 \(K - t\)；当 \(j\) 取 \([r_k + 1, r_k + K - t]\) 时，产生的贡献分别为 \(K - t - 1, K - t - 2, \ldots, 1\)。区间加一个数可以一阶差分处理，区间加等差数列可以二阶差分。
-
若 \(r_k - l_k + 1 < K\)，当 \(j\) 取 \([l_k + t, r_k]\) 时，产生的贡献分别为 \(1, 2, \ldots, r_k - l_k + 1 - t\)；当 \(j\) 取 \([r_k + 1, l_k + K - 1]\) 时，产生的贡献均为 \(r_k - l_k + 1 - t\)；当 \(j\) 取 \([l_k + K, r_k + K - t]\) 时，产生的贡献分别为 \(r_k - l_k - t, r_k - l_k - t - 1, \ldots, 1\)。
二阶差分一下，最后枚举 \(j\) 取 \(\max\)。时间复杂度 \(O(n(n + m))\)。
code
// Problem: E. Two Editorials
// Contest: Codeforces - Educational Codeforces Round 98 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1452/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 4040;
int n, m, K, a[maxn], b[maxn], d[maxn], e[maxn];
void solve() {
scanf("%d%d%d", &n, &m, &K);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &a[i], &b[i]);
}
int ans = 0;
for (int i = 1; i <= n - K + 1; ++i) {
mems(d, 0);
mems(e, 0);
int s = 0;
for (int j = 1; j <= m; ++j) {
int t = max(0, min(i + K - 1, b[j]) - max(i, a[j]) + 1), p = min(K, b[j] - a[j] + 1);
s += t;
if (t == p) {
continue;
}
int l = a[j] + t, r = min(b[j], a[j] + K - 1);
if (l <= r) {
++d[l];
--d[r + 1];
d[r + 1] -= r - l + 1;
d[r + 2] += r - l + 1;
}
if (p == K) {
if (b[j] - a[j] >= K) {
e[a[j] + K] += K - t;
e[b[j] + 1] -= K - t;
}
e[b[j] + 1] += K - t;
e[b[j] - t + K] -= K - t;
--d[b[j] + 1];
++d[b[j] - t + K];
d[b[j] - t + K] += K - t - 1;
d[b[j] - t + K + 1] -= K - t - 1;
} else {
int len = b[j] - a[j] + 1;
e[b[j] + 1] += len - t;
e[a[j] + K] -= len - t;
e[a[j] + K] += len - t;
e[b[j] + K - t] -= len - t;
--d[a[j] + K];
++d[b[j] + K - t];
d[b[j] + K - t] += len - 1 - t;
d[b[j] + K - t + 1] -= len - 1 - t;
}
}
for (int j = 1; j <= n; ++j) {
d[j] += d[j - 1];
e[j] += e[j - 1];
}
for (int j = 1; j <= n; ++j) {
d[j] += d[j - 1];
}
// printf("i: %d\n", i);
for (int j = K; j <= n; ++j) {
// printf("%d %d %d %d\n", j, s, d[j], e[j]);
ans = max(ans, s + d[j] + e[j]);
}
}
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}