题目描述

在聪明核桃某年某月的月赛中，一共有 $n$ 道比赛题（题目编号从 $1$ 到 $n$ ），一共有 $m$ 位同事参加了这次月赛（同事的编号从 $1$ 到 $m$）。

月赛比完之后需要讲解，于是小核桃找到了禾木和桃子来给大家讲解其中的一些题目，讲解的时间是有限的，所以禾木和桃子都最多只能选择连续的 $k$ 道题目进行讲解。他俩讲解的题目可以有相同的，但是必须保证每个人讲解的题目编号是连续的，且题目数量不超过 $k$ 道。

每一位同事感兴趣的题目不尽相同，第 $i$ 位同事只对编号从 $l_i$ 到 $r_i$ 的题目感兴趣（包括 $l_i$ 和 $r_i$）。同时，每一位同事只能选择听一个人的讲解，也就是说 —— 如果某位同事选择听禾木的讲解他就听不了桃子的讲解，如果选择听桃子的讲解他就听不了禾木的讲解。每一位同事都会选择去听讲解的题目中他感兴趣的题目数较多的那个讲解。举个例子：对于某位同事，如果禾木讲解的题目中有 $3$ 道他感兴趣的题目，而桃子讲解的题目中只有 $2$ 道他感兴趣的，则他会选择去听禾木的讲解。如果禾木和桃子讲解的题目中他感兴趣的题目数相同，则他会任意选择其中一个讲解去听。对于第 $i$ 位同事，我们定义他所选择的讲座中会讲到的他感兴趣的题目数量为 $a_i$。

小核桃希望确定一下禾木和桃子所讲解的问题，使得所有同事听到的感兴趣的题目数之和（即 $\sum\limits_{i=1}^m a_i$）最大，请你帮助他解决这个问题。

输入格式

输入的第一行包含三个整数 $n,m,k(1 \le n,m \le 2000, 1 \le k \le n)$，以空格分隔，分别表示比赛题目的数量，参加比赛的同事的数量，以及禾木与桃子最多能讲解的题目的数量。
接下来 $m$ 行，每行包含两个整数，其中第 $i+1$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 位同事感兴趣的题目范围。

输出格式

输出一个整数，表示最大的所有同事听到的感兴趣的题目数之和（即 $\sum\limits_{i=1}^m a_i$）。

样例

10 5 3
1 3
2 4
6 9
6 9
1 8

14

10 3 3
2 4
4 6
3 5

8

4 4 1
3 3
1 1
2 2
4 4

2

5 4 5
1 2
2 3
3 4
4 5

8

样例解释

• 样例1中可以选择一个人讲第 $1$ 到 $3$ 题，另一个人讲第 $6$ 到 $8$ 题，则 $a_i$ 对应的序列为 $[3,2,3,3,3]$；
• 样例2中可以选择一个人讲第 $2$ 到 $4$ 题，另一个人讲第 $4$ 到 $6$ 题；
• 样例3中可以选择一个人讲第 $1$ 题，另一个人讲第 $2$ 题，或者选第 $3$、$4$ 题也可以，在这个样例中只要禾木和桃子选择讲的题目不一样就能够或者最大值 $2$。
• 样例4中两个人都只能选择讲第 $1$ 到 $5$ 题。

数据范围

• 对于 $20\%$ 的数据，$n,m \le 20$；
• 对于 $60\%$ 的数据，$n,m \le 200$；
• 对于 $100\%$ 的数据，$1 \le n,m \le 2000, 1 \le k \le n$。