P14410 [JOISC 2015] 钥匙 / Keys

你知道 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$ 内，通过合理管理门锁开关，门锁关闭的总时间的最大值。

在该输入输出示例中，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 完成