Уборка дороги
Вдоль дороги длиной метров расположены дома. Жители подают заявки на уборку снега. Заявка задаёт начало участка — расстояние в метрах от начала дороги — и длину участка в метрах.
Если участки двух заявок имеют общую часть дороги, выполнить можно только одну из этих заявок. Если же конец одного участка совпадает с началом другого, выполнить можно обе.
Определите наибольшее количество заявок, которые можно выполнить, и минимально возможную при таком количестве длину неубранного участка в конце дороги — расстояние от конца последнего убранного участка до конца дороги.
Входные данные
В первой строке находится число — количество заявок (натуральное число, не превышающее 2000). Каждая из следующих строк содержит два натуральных числа, не превышающих : начало участка (в метрах от начала дороги) и его длину.
Заявки идут в произвольном порядке и могут повторяться. Гарантируется, что конец каждого участка не выходит за пределы дороги.
Выходные данные
Выведите два целых числа: сначала наибольшее количество заявок, которые можно выполнить, затем минимально возможную при таком количестве длину неубранного участка в конце дороги.
Примеры
5 1 1000 1001 1000 2001 2500 4501 500 4501 1500
4 3999
4 4 3 1 3 7 9993 2 8
3 0
Примечание
В первом примере можно выполнить четыре заявки. Для минимального неубранного конца следует выбрать участок длиной 1500, а не 500: уборка закончится на отметке 6001. Останется 3999 метров. Во втором примере участки [1; 4], [4; 7] и [7; 10000] совместимы.