题目描述

译自 JOISC 2015 Day2 T2「Keys」。

JOI 社有 $N$ 个社员，从 $1$ 到 $N$ 编号。社员出勤时间从时刻 $0$ 到时刻 $M$。保证在时刻 $0$ 和时刻 $M$ 的时候，全体社员都在公司内。

今天，每个社员会恰好离开公司一次。第 $i$ 个社员会在时刻 $S_i$ 时刻离开公司，会在 $T_i$ 时刻回到公司。保证不会同时有 $2$ 个人同时离开或者回到公司。

JOI 社会社大楼有一个大门作为入口，所有社员必须从这个门进出公司。在公司内部可以自由的打开或者关闭这个门。但是在公司外的话，必须有钥匙才能打开或者关闭这个门。在时刻 $0$，门是关闭的。因此，第 $i$ 个社员能在 $T_i$ 时刻回到公司，当且仅当在 $T_i$ 时刻的时候门开着，或者他有钥匙。

现在你有 $K$ 把钥匙，你需要把这些钥匙给其中 $K$ 个社员，使得第 $i$ 个社员在 $T_i$ 时刻都能够进入公司，并且从 $0$ 时刻到 $M$ 时刻，门被关着的时间最大。

输入格式

第一行包含三个整数 $N, M, K$，表示社员个数，总共出勤时间和钥匙的个数。

接下来 $N$ 行，每行包含两个整数 $S_i$ 和 $T_i$，表示社员 $i$ 在 $S_i$ 时刻离开公司，会在 $T_i$ 时刻回到公司。

输出格式

输出一个整数，表示从 $0$ 时刻到 $M$ 时刻，门被关着的时间的最大值。

样例 1

4 20 2
3 11
5 15
6 10
12 18

13

总共有 $4$ 个人，其中给社员 $2$ 和社员 $4$ 各一把钥匙，门关着的时间最多是 $13$，具体操作如下：

• 在时刻 $0$，门关着；
• 在时刻 $3$，社员 $1$ 离开公司，因为没有钥匙，门开着；
• 在时刻 $5$，社员 $2$ 离开公司，因为持有钥匙，门被关上了；
• 在时刻 $6$，社员 $3$ 离开公司，因为没有钥匙，门开着；
• 在时刻 $10$，社员 $3$ 回到公司，但是让门开着；
• 在时刻 $11$，社员 $1$ 回到公司，门被关上了；
• 在时刻 $12$，社员 $4$ 离开公司，因为持有钥匙，门被关上了；
• 在时刻 $15$，社员 $2$ 回到公司，门被关上了；
• 在时刻 $18$，社员 $4$ 回到公司，门被关上了；
• 在时刻 $20$，门保持关闭状态。

20 100000 8
29930 89724
56133 70462
28063 78568
32483 64351
9410 20176
55809 62944
32450 85190
73536 73966
20452 78868
45458 63484
8286 47425
76018 81622
16736 49308
85383 94641
25100 40002
22158 22821
23508 41781
61709 98882
58110 78431
28448 89247

72454

数据范围与提示

对于全部数据，满足 $1 \le N \le 2000, 1 \le M \le 10^9, 1 \le K < N, 0 < S_i < T_i < M, \forall 1 \le i < j \le N, S_i \ne S_j, S_i \ne T_j, T_i \ne T_j$。

本题共有 $2$ 个子任务。每个子任务的分数和附加限制如下：