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