Ю. Дрождинин
На складе магазина игрушек есть отдел с некоторым количеством различных по размеру кубиков. Ночной сторож решил немного прибраться в этом отделе, собрав часть кубики в башни. Кубики нумеруются по мере поступления на склад. Один кубик можно поставить на другой, если длина его ребра хотя бы на 2 единицы меньше длины ребра нижнего кубика. Сначала сторож построил башню максимальной высоты, затем из оставшихся кубиков по тому же принципу – вторую башню и т. д. Определите высоту самой низкой башни и сумму номеров самых верхних кубиков во всех башнях.
Входные данные представлены в файле 26-190.txt следующим образом. В первой строке входного файла записано число N – количество кубиков на складе (1 ≤ N ≤ 10 000). В каждой из следующих N строк записаны номер и длина ребра одного кубика – натуральные числа, не превосходящие 10 000.
Запишите в ответе два целых числа: сначала высоту самой низкой башни, затем – сумму номеров самых верхних кубиков во всех башнях.
Пример входного файла:
7
1 20
2 10
3 15
4 19
5 7
6 11
7 12
При таких исходных данных все кубики можно объединить в две башни. В первую войдут кубики с номерами 1, 3, 7, 2 и 5, а во вторую – кубики с номерами 4 и 6. Высота второй (самой низкой) башни равна 19 + 11 = 30 единиц, а сумма номеров верхних кубиков 5 + 6 = 11. Ответ: 30 11.