Задание выполняется с испоьлзованием прилагаемых файлов
Вдоль дороги длиной 10 км расположены дома. В течение дня жители отправляют в управляющую компанию заявки на уборку снега. В каждой заявке указано, с какой точки (в метрах от начала дороги) нужно начать уборку и какова длина участка (в метрах), который требуется очистить.
Если участки дороги в двух или более заявках имеют общую часть дороги, то можно выполнить не более одной из таких заявок. Если
конец одного участка совпадает с началом другого, то нужно убрать оба участка.
Определите наибольшее количество заявок, которые может выполнить управляющая компания, и в этом случае максимальную длину неубранного участка дороги между двумя последними убранными участками (в метрах).
Входные данные
Первая строка входного файла содержит целое число N (N ⩽ 2000) - количество заявок на уборку снега. Следующие N строк содержат
пары чисел, обозначающих начало участка (в метрах от начала дороги) и его протяжённость. Каждое из чисел натуральное, не
превосходящее 10 000. Гарантируется, что конец участка не выходит за пределы дороги.
В ответе запишите два целых числа: сначала наибольшее количество заявок, которые может выполнить управляющая компания, затем - минимально возможную при таком количестве заявок длину неубранного участка, расположенного конце дороги (в метрах).
Типовой пример организации данных во входном файле
5
1 1000
1001 1000
2001 1000
2001 2500
4501 500
При таких исходных данных будет выполнено не более 4 заявок. Могут быть выполнены заявки с номерами 1, 2, 4 и 5 или заявки с номерами 1, 2, 3 и 5. Ответ: 4 1500.