Входной файл содержит сведения о заявках на проведение лекций в просторной аудитории. В каждой заявке указаны время начала и время окончания (в минутах от начала суток) лекции. Если время начала одной лекции меньше времени окончания другой, то провести можно только одну из них. Если время окончания одной лекции совпадает со временем начала другой, то провести можно обе. Кроме того, после каждой третьей проведённой в аудитории лекции необходимо проводить влажную уборку, которая занимает 10 минут или более. В этом случае между концом последней проведённой лекции и началом следующей должно пройти не менее, чем 10 минут, а сама уборка начинается немедленно после конца последней проведённой лекции и занимает всё то время, пока аудитория свободна. Определите, какое максимальное количество лекций можно провести в аудитории и какая можеть быть при этом максимально возможная длительность самой последней по счёту уборки аудитории.
Входные данные
В первой строке входного файла находится натуральное число N (N⩽1000) – количество заявок на проведение лекций. Следующие N строк содержат пары чисел, обозначающие время начала и время окончания каждой лекции. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество лекций и максимально возможную длительность последней уборки.
Типовой пример организации данных во входном файле
9
10 20
19 30
25 30
30 40
43 48
50 66
70 82
62 65
65 100
При таких исходных данных можно провести максимум пять мероприятий, например, мероприятия по заявкам 1, 3, 4, затем уборка, 6 и 7. Максимально возможное начало самой последней уборки равно 22, если выбрать мероприятия в следующем порядке: 1, 3, 4, уборка с 40 минуты по 62, 8 и 9.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.