2999 「JOISC 2015 Day2」Keys

译自 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 $ 时刻，门被关着的时间的最大值。

总共有 $ 4 $ 个人，其中给社员 $ 2 $ 和社员 $ 4 $ 各一把钥匙，门关着的时间最多是 $ 13 $，具体操作如下： + 在时刻 $ 0 $，门关着； + 在时刻 $ 3 $，社员 $ 1 $ 离开公司，因为没有钥匙，门开着； + 在时刻 $ 5 $，社员 $ 2 $ 离开公司，因为持有钥匙，门被关上了； + 在时刻 $ 6 $，社员 $ 3 $ 离开公司，因为没有钥匙，门开着； + 在时刻 $ 10 $，社员 $ 3 $ 回到公司，但是让门开着； + 在时刻 $ 11 $，社员 $ 1 $ 回到公司，门被关上了； + 在时刻 $ 12 $，社员 $ 4 $ 离开公司，因为持有钥匙，门被关上了； + 在时刻 $ 15 $，社员 $ 2 $ 回到公司，门被关上了； + 在时刻 $ 18 $，社员 $ 4 $ 回到公司，门被关上了； + 在时刻 $ 20 $，门保持关闭状态。

对于全部数据，满足 $ 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,i\neq j$，有 $S_i \ne S_j, S_i \ne T_j, T_i \ne T_j$。

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