問題
背景
鳗鱼王国的学生们总是在学校地下的学生活动室中学习。学生活动室由于总是有学生在,所以平时打扫得很干净,但到了暑假学生不来学校时,学生活动室就会布满灰尘。因此学生们决定即使在暑假期间也来学校打扫学生活动室。然而学生们能来学校的日子有限,并且不太想来学校。于是暂时决定让每个学生都打扫一次,但这还不够,所以需要让部分学生每天都来学校。如何分配才能保持学生活动室的整洁呢?
課題
当将清洁工作分配给学生,使得最长未清洁的时间最短时,请回答该时间为多少天。
学生人数 N暑假的天数 M参数 K 。 i 第几位学生 ai 减去 bi 只能在……期间来学校。此外,每个学生只能被安排清洁一次。但是 K 可以随便选择……名学生,并让这些学生在他们能来学校的期间每天都来学校帮忙清洁。
配点
200
入力
输入按以下格式给出。
N M K a1 b1 ... aN bN
N 是学生人数,M 是暑假的天数,K 是每天来学校的学生人数,ai,bi 是 您也可以写 i 表示第几位学生能够来学校的期间。
制約
输入中的每个变量都满足以下约束。
- 1 \leq N \leq 105
- 1 \leq M \leq 109
- 0 \leq K \leq N
- 1 \leq ai \leq bi \leq M
部分点
针对此问题设置了部分分数。这个问题的测试用例50这些点还满足以下约束。
- K=0
出力
问题的解决办法 在1行输出。 没有
入力例1
1 2 0 1 2
输入示例 1 的输出示例 路径
2
1第……天当值时也会2第……天当值时最长间隔会是2天。
図 1
入力例2
1 2 1 1 2
输入示例 2 的输出示例
1
因为可以每天来学校,所以最长的间隔是1天。
図 2
入力例3
2 6 1 2 2 4 5
输入示例 3 的输出示例
2
図 3