Фермер Джон открыл бассейн для своих коров, чтобы они там отдыхали и потом
давали больше молока.
Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из
которых работает в течение некоторого интервала времени в течение дня. Для простоты,
бассейн открыт с момента времени \(t=0\) до момента времени \(t = 1,000,000,000\)
каждый день. Поэтому каждый интервал может быть описан двумя целыми числами
- временем начала и конца работы спасателя. Например, спасатель, начинающий в
момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает
интервал в три единицы времени.
К несчастью, ФД нанял на одного спасателя больше чем может платить зарплату.
При условии, что он должен уволить одного спасателя, какой максимальный интервал
времени, будет покрыт оставшимися спасателями? Интервал времени покрыт, если
присутствует хоть один спасатель в это время.
ФОРМАТ ВВОДА (файл lifeguards.in):
Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100,000\)). Каждая из последующих
\(N\) строк описывает интервалы работы спасателей двумя целыми числами в интервале
\(0 \ldots 1,000,000,000\), задающими начало и конец работы спасателя. Все числа концы
интервалов - различны. Сами интервалы могут перекрываться.
ФОРМАТ ВЫВОДА (файл lifeguards.out):
Выведите одно целое число - максимальное количество времени, которое останется
покрытым, если ФД уволит одного спасателя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 9
1 4
3 7
|
7
|