AT_joisc2015_f 合鍵

## JOISC2015 Day2T2 锁 在 JOI 公司内共有 $N$ 个员工。在时刻 $0$ ，每一个员工均在公司内。公司只有一个大门用于进出公司，这个大门可以上锁。在公司内的人可以任意开锁或锁门，但在公司外只有拥有备用钥匙的人可以任意开锁或锁门。因为 JOI 公司的规定，在公司内的人除非要从公司出去，是不允许开门锁的。 现在员工 $i$ 会在 $S_i$ 时刻从公司出外出差，在 $T_i$ 时刻回到公司，保证在同一时刻没有两个或以上的员工同时进出大门，且在 $M$ 时刻所有员工均回到了公司，即 $T_i < M$ 。你可以让 $K$ 个员工拿到备用钥匙，为了不让钥匙丢失，备用钥匙不能给其他员工借用。 现在 JOI 公司的社长需要你求出：在所有员工到达公司时都能进入公司（即门没有上锁或者这个员工有备用钥匙）、拥有备用钥匙的员工不超过 $K$ 的情况下，在这 $M$ 个单位时间内门最多锁住多长时间。

第一行三个正整数 $N,M,K$，接下来 $N$ 行每行两个正整数 $S_i , T_i$

一行一个正整数表示最大的给门上锁的时间。

$1 \leq K \leq N \leq 2000$ $1 \leq M \leq 10^9$ $0 < S_i < T_i < M$，$S_i,T_i$ 两两不同