A13899 | 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.

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.

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