Задание 26

Вдоль дороги длиной 10 км расположены дома.

В течение дня жители отправляют в управляющую компанию заявки на уборку снега.

В каждой заявке указано, с какой точки (в метрах от начала дороги) нужно начать уборку и какова длина участка (в метрах), который требуется очистить.

Если участки дороги в двух или более заявках имеют общую часть дороги, то можно выполнить не более одной из таких заявок.

Если

конец одного участка совпадает с началом другого, то нужно убрать оба участка.

Определите, наибольшее количество заявок, которые может выполнить управляющая компания, и в этом случае минимальную длину неубранного участка, расположенного в конце дороги (в метрах).

Входные данные

Первая строка входного файла содержит целое число N (N ⩽ 2000) - количество заявок на уборку снега.

Следующие N строк содержат

пары чисел, обозначающих начало участка (в метрах от начала дороги) и его протяжённость.

Каждое из чисел натуральное, не

превосходящее 10 000.

Гарантируется, что конец участка не выходит за пределы дороги.

В ответе запишите два целых числа: сначала наибольшее количество заявок, которые может выполнить управляющая компания, затем - минимально возможную при таком количестве заявок длину неубранного участка, расположенного конце дороги (в метрах).

Типовой пример организации данных во входном файле

5

1 1000

1001 1000

2001 2500

4501 500

4501 1500

При таких исходных данных будет выполнено не более 4 заявок.

Могут быть выполнены заявки с номерами 1, 2, 3 и 4 или заявки с номерами 1, 2, 3 и 5.

Ответ: 4 3999.