Задача #1921

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

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

В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество заявок на проведение волшебных поединков. Следующие N строк содержат пары чисел, обозначающих время начала и длительность волшебного поединка. Каждое из чисел натуральное, не превосходящее 1440.

Запишите в ответе два числа: максимальное количество поединков, которое можно провести на магической фонтанной площади и самый длинный перерыв между двумя последними волшебными поединками (в минутах).

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

5
20 120
90 20
147 43
150 30
120 20

При таких исходных данных можно провести максимум три поединка, например, по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними поединками составит 10 мин., если состоятся поединки по заявкам 2, 4 и 5.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.