P14595 [COCI 2025/2026 #2] 集训 / Dodatna

本题满分 $70$。

有 $n$ 名学生，第 $i$ 名学生从每天的第 $l_i$ 毫秒初到每天的第 $r_i$ 毫秒初（第 $(r_i-1)$ 毫秒末）在学校内。 现在要选择一段连续的时间上 OI 课，要求是： - 所有上课的学生在上课时间内必须全程在学校。 - 至少有 $k$ 人上课。 请输出 OI 课能持续的最长时间（单位：毫秒）。特别地，若无解，输出 $0$。

第一行，两个正整数 $n,k$（$1\le n,k\le 3\times 10^5$）。 接下来 $n$ 行，第 $i$ 行两个整数 $l_i,r_i$（$1\le l_i\lt r_i\le 86\, 400\, 000$）。

输出一行一个非负整数，表示答案。 特别地，若无解，输出 $0$。

### 样例解释 **样例二解释**：在第 $6,7,8$ 毫秒上课，一共可以上 $3$ 毫秒。 ### 子任务 - $\text{Subtask 1 (13 pts)}$：$k=1$； - $\text{Subtask 2 (27 pts)}$：$1\le n\le 1000$，$k=2$； - $\text{Subtask 3 (11 pts)}$：$r_i\le 100$； - $\text{Subtask 4 (19 pts)}$：无额外限制。