Have you had coffee with Kurt recently? Maybe you should.
Coffee with Kurt is very simple. of Kurt's friends tell Kurt when they're
available, and Kurt schedules coffee for a single interval of time.
Kurt doesn't want to drink coffee by himself though, so he will only
schedule an interval of time where, at every instant in time inside the given
interval, at least of Kurt's friends will be free to drink coffee
with him. Note that people are welcome to leave and join depending on their
availability, Kurt just needs at least
people at all points in time,
otherwise he will get lonely.
For each possible value of from
to
, help Kurt find the longest
interval of time he can schedule coffee for.
Constraints
Subtask 1 [1 point]
Subtask 2 [1 point]
No additional constraints.
Input Specification
The first line contains a single integer, .
The next lines each contain two integers,
and
, indicating
that friend
is free from time
to time
inclusive.
Output Specification
Output integers. The
integer should be the maximum length of the longest interval that Kurt can schedule coffee for given he wants
to get coffee with
people. If it is not possible to get coffee with at
least
people, output
.
Sample Input 1
3
1 39
17 1000
1001 1002
Sample Output 1
999 22 0
Sample Explanation 1
If Kurt schedules coffee from time to time
, he can get coffee with
at least one friend at every point of time within. If Kurt schedules coffee from time
to time
, he can get coffee with both the first and second
friend. It is not possible for him to get coffee with all three friends
simultaneously - there will not be anyone in the time range
available for Kurt to get coffee with.
Comments