CF1452E Two Editorials

Berland 的 ICPC 刚刚结束了。有 $m$ 名编号为 $1$ 到 $m$ 的选手，就编号 $1$ 到 $n$ 的题目进行比赛。 现在题解即将公开。有两名出题人要讲题，每个人要讲**连续**的 $k$ 道题，这两人都会独立选取他们要讲的 $k$ 个题，这 $k$ 个题所构成的区间可以相交，包含或相离。 第 $i$ 名选手对第 $l_i$ 到第 $r_i$ 道题感兴趣，每一名选手都只能听一个出题人讲的题，来最大化他听的他感兴趣的题的数目。设每个人的这个最大值为 $a_i$。注意，选手只能选择听一个出题人讲题，即便出题人讲的题是不相交的。 两位出题人想选择每个人讲的题，以最大化 $a_i$ 的和。

第一行输入三个整数 $n,m,k$，分别表示题的数目，选手的数目和出题人讲的题的区间长度。 接下来 $m$ 行，第 $i$ 行输入两个整数 $l_i,r_i$，表示第 $i$ 名选手感兴趣的题目区间。 $1 \le n,m \le 2000$，$1 \le k \le n$，$1 \le l_i \le r_i \le n$。

输出一个整数即 $a$ 的和的最大值。

对于第一个样例，第一名出题人讲题目 $1$ 到 $3$，第二名出题人讲题目 $6$ 到 $8$。这样，$\{a\} = {3,2,3,3,3}$，注意最后一名选手只能听一个出题人讲课。 对于第二个样例，第一名出题人讲题目 $2$ 到 $4$，第二名讲题目 $4$ 到 $6$。 对于第三个样例，第一名出题人讲题目 $1$，第二名讲题目 $2$；或者第一名出题人讲题目 $4$，第二名讲题目 $3$，这些方案都得到结果 $2$。 对于第四个样例，第一名出题人讲题目 $1$ 到 $5$，第二名也讲题目 $1$ 到 $5$。