题目描述

你知道 Just Odd Inventions 公司吗？该公司的业务是“仅仅奇妙的发明（just odd inventions）”，在此简称为 JOI 公司。

JOI 公司有 $N$ 名员工，编号从 1 到 $N$。所有员工在时刻 0 到时刻 $M$ 之间工作，时刻 0 和时刻 $M$ 时，所有员工必须在公司内部。

今天，巧合的是，每位员工恰好外出一次。员工 $i$（$1 \le i \le N$）在时刻 $S_i$ 离开公司，在时刻 $T_i$ 返回公司。没有任何两名员工在同一时刻进出公司。

JOI 公司入口处有一扇大门，员工只能通过这扇门进出公司。门上装有锁，锁可以处于开启或关闭状态。公司内部人员可以自由开关锁，但公司外部人员只能由持有钥匙的人开关锁。在时刻 0，门锁处于关闭状态。

每位员工在返回公司时，必须能够进入公司。也就是说，对于任意员工 $i$（$1 \le i \le N$），必须满足：员工 $i$ 持有钥匙，或者在时刻 $T_i$ 时门锁处于开启状态，二者至少满足其一。当员工返回公司时，以及持有钥匙的员工离开公司时，可以选择是否关闭门锁。没有钥匙的员工离开公司时，不允许关闭门锁。

JOI 公司的社长决定将钥匙交给 $K$ 名员工。为了避免钥匙丢失，员工之间不能互相传递钥匙。此外，JOI 公司的社长重视工作效率，因此员工除了自己进出公司时，不得随意开关门锁。

出于安全考虑，社长希望在工作时间 $M$ 内，门锁关闭的总时间尽可能长。

题目

给定员工的进出时间信息，以及被授予钥匙的员工数量 $K$，编写一个程序，求在合理管理门锁开关的情况下，门锁在工作时间 $M$ 内关闭的总时间的最大值。

输入格式

从标准输入读入以下数据：

• 第一行包含三个整数 $N, M, K$，以空格分隔。表示 JOI 公司有 $N$ 名员工，所有员工在时刻 0 到时刻 $M$ 之间工作，其中 $K$ 名员工将被授予钥匙。
• 接下来的 $N$ 行，第 $i$ 行（$1 \le i \le N$）包含两个整数 $S_i, T_i$，以空格分隔。表示员工 $i$ 在时刻 $S_i$ 离开公司，在时刻 $T_i$ 返回公司。

输出格式

在标准输出上，输出一行，表示在工作时间 $M$ 内，通过合理管理门锁开关，门锁关闭的总时间的最大值。

4 20 2
3 11
5 15
6 10
12 18

13

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

提示

在该输入输出示例中，JOI 公司有 4 名员工，其中 2 名员工被授予钥匙。若将钥匙交给员工 2 和员工 4，并按以下方式操作，则门锁关闭的总时间为 13：

• 时刻 0，门锁处于关闭状态。
• 时刻 3，员工 1 离开公司。由于员工 1 未持有钥匙，无法关闭门锁。
• 时刻 5，员工 2 离开公司，并关闭门锁。
• 时刻 6，员工 3 离开公司。由于员工 3 未持有钥匙，无法关闭门锁。
• 时刻 10，员工 3 返回公司，门锁保持开启状态。
• 时刻 11，员工 1 返回公司，并关闭门锁。
• 时刻 12，员工 4 离开公司，并关闭门锁。
• 时刻 15，员工 2 返回公司，并关闭门锁。
• 时刻 18，员工 4 返回公司，并关闭门锁。
• 时刻 20 之前，门锁一直处于关闭状态。

门锁关闭的总时间无法超过 13，因此输出 13。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 2000$
• $1 \le M \le 1000000000$
• $1 \le K < N$
• $0 < S_i < T_i < M$（$1 \le i \le N$）
• 对任意 $i, j$（$1 \le i \le N, 1 \le j \le N, i \ne j$），满足 $S_i \ne S_j, S_i \ne T_j, T_i \ne T_j$

子任务

子任务 1 [10 分]

• $N \le 20$
• $M \le 1000000$

子任务 2 [90 分]

无额外限制。

翻译由 Qwen3-235B 完成