Задача 10 из 21

Уборка дороги

Время 2 с · память 256 МБ

Вдоль дороги длиной 10 00010\,000 метров расположены дома. Жители подают заявки на уборку снега. Заявка задаёт начало участка — расстояние в метрах от начала дороги — и длину участка в метрах.

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

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

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

В первой строке находится число NN — количество заявок (натуральное число, не превышающее 2000). Каждая из следующих NN строк содержит два натуральных числа, не превышающих 10 00010\,000: начало участка (в метрах от начала дороги) и его длину.

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

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

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

Примеры

Ввод 1
5
1 1000
1001 1000
2001 2500
4501 500
4501 1500
Вывод 1
4 3999
Ввод 2
4
4 3
1 3
7 9993
2 8
Вывод 2
3 0

Примечание

В первом примере можно выполнить четыре заявки. Для минимального неубранного конца следует выбрать участок длиной 1500, а не 500: уборка закончится на отметке 6001. Останется 3999 метров. Во втором примере участки [1; 4], [4; 7] и [7; 10000] совместимы.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче