CF1452E.Two Editorials

Berland regional ICPC contest has just ended. There were $m$ participants numbered from $1$ to $m$, who competed on a problemset of $n$ problems numbered from $1$ to $n$.

Now the editorial is about to take place. There are two problem authors, each of them is going to tell the tutorial to exactly $k$ consecutive tasks of the problemset. The authors choose the segment of $k$ consecutive tasks for themselves independently of each other. The segments can coincide, intersect or not intersect at all.

The $i$-th participant is interested in listening to the tutorial of all consecutive tasks from $l_i$ to $r_i$. Each participant always chooses to listen to only the problem author that tells the tutorials to the maximum number of tasks he is interested in. Let this maximum number be $a_i$. No participant can listen to both of the authors, even if their segments don't intersect.

The authors want to choose the segments of $k$ consecutive tasks for themselves in such a way that the sum of $a_i$ over all participants is maximized.

Berland 地区 ICPC 竞赛刚刚结束。共有 $m$ 名参赛者，编号从 $1$ 到 $m$，他们共同完成了由 $n$ 道题目组成的题目集，题目编号从 $1$ 到 $n$。

现在即将举行题解讲解环节。共有两位题目作者，每位作者将分别讲解题目集中恰好 $k$ 道连续题目的题解。两位作者各自独立地为自己选择一段长度为 $k$ 的连续题目区间。这两段区间可以完全重合、部分相交，也可以互不相交。

第 $i$ 名参赛者希望听取从第 $l_i$ 题到第 $r_i$ 题（含端点）的所有连续题目的题解。每名参赛者总是选择唯一一位作者来听取其讲解——该作者所讲解的题目中，落在 $[l_i, r_i]$ 范围内的题目数量最多。记该最大数量为 $a_i$。即使两位作者所选区间互不相交，任何一名参赛者也不能同时听取两位作者的讲解。

两位作者希望为自己选择两段长度为 $k$ 的连续题目区间，使得所有参赛者的 $a_i$ 之和最大化。

The first line contains three integers $n, m$ and $k$ ($1 \le n, m \le 2000$, $1 \le k \le n$) — the number of problems, the number of participants and the length of the segment of tasks each of the problem authors plans to tell the tutorial to.

The $i$-th of the next $m$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the segment of tasks the $i$-th participant is interested in listening to the tutorial to.

第一行包含三个整数 $n, m$ 和 $k$（$1 \le n, m \le 2000$，$1 \le k \le n$）——分别表示题目数量、参与者数量，以及每位题目作者计划讲解的题目区间的长度。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）——表示第 $i$ 位参与者希望听取讲解的题目区间。

Print a single integer — the maximum sum of $a_i$ over all participants.

输出一个整数——所有参与者中 $a_i$ 的最大和。

In the first example the first author can tell the tutorial to problems from $1$ to $3$ and the second one — from $6$ to $8$. That way the sequence of $a_i$ will be $[3, 2, 3, 3, 3]$. Notice that the last participant can't listen to both author, he only chooses the one that tells the maximum number of problems he's interested in.

In the second example the first one can tell problems $2$ to $4$, the second one — $4$ to $6$.

In the third example the first one can tell problems $1$ to $1$, the second one — $2$ to $2$. Or $4$ to $4$ and $3$ to $3$. Every pair of different problems will get the same sum of $2$.

In the fourth example the first one can tell problems $1$ to $5$, the second one — $1$ to $5$ as well.

在第一个例子中，第一位作者可以讲解第 $1$ 至 $3$ 题，第二位作者可以讲解第 $6$ 至 $8$ 题。这样，序列 $a_i$ 将为 $[3, 2, 3, 3, 3]$。注意：最后一名参与者不能同时听两位作者的讲解，他只会选择其中能为其讲解更多其感兴趣题目的那位作者。

在第二个例子中，第一位作者可以讲解第 $2$ 至 $4$ 题，第二位作者可以讲解第 $4$ 至 $6$ 题。

在第三个例子中，第一位作者可以讲解第 $1$ 题，第二位作者可以讲解第 $2$ 题；或者第一位作者讲解第 $4$ 题，第二位作者讲解第 $3$ 题。任意一对不同的题目所获得的总和均为 $2$。

在第四个例子中，第一位作者可以讲解第 $1$ 至 $5$ 题，第二位作者也可以讲解第 $1$ 至 $5$ 题。