레이팅 미적용The famous mentor Jakov loves teaching and helping diligent students. This school
year he decided to help some truly unusual students and teach additional computer
science classes. Namely, each of the \(n\) students has very strange requirements that
must be satisfied for them to even show up to the extra class, but more on that
another time.
Jakov’s conditions for holding the extra class are much simpler and are as follows:
• All students who will attend the extra class must be in the school from
the beginning to the end of the extra class.
• There must be at least \(k\) students in the extra class, otherwise it will not be
held at all.
With the help of the principal, Jakov discovered the schedules of all \(n\) students, and for each student
\(i\) (\(1 \le i \le n\)) he knows that they are in the school between the \(l_{i}-th\) and \(r_{i}-th\) millisecond of the day
(exclusively).
Help Jakov by answering the question: what is the maximum possible duration of the extra class he can
hold? If Jakov cannot hold an extra class at all, output the number 0.
The first millisecond during which student \(i\) is in the school is \(l_{i}\), and the last is \(r_{i} - 1\).
The first line contains the natural numbers \(n\) and \(k\) (\(1 \le n\), \(k \le 3 \cdot 10^{5}\)) from the problem statement.
Each of the following \(n\) lines contains 2 numbers \(l_{i}\) and \(r_{i}\) (\(1 \le l_{i} < r_{i} \le 86\,400\,000\)), from the problem
statement.
In the first and only line, output a single number — the maximum duration of the extra class that Jakov
can organize, or 0 if it is impossible.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 13점 | \(K = 1\) |
2 | 27점 | \(1 \le N \le 1000\), \(K = 2\) |
3 | 11점 | \(r_{i} \le 100\) |
4 | 19점 | No additional constraints. |
5 1
1 3
1 4
1 5
1 6
1 765 2
6 10
8 14
5 9
5 6
4 63Clarification of the second example: The longest duration of the extra class that Jakov can organize
is 3 seconds because the 1st and 3rd student will attend it in the 6th, 7th, and 8th second.