Входной файл содержит сведения о поставках товаров в магазин. В каждой записи указано планируемое время начала и время завершения принятия поставки. Если время начала поставки одной партии меньше времени завершения поставки другой, то принимается только одна из них. Если время начала поставки партии совпадает с временем завершения поставки другой, то принимаются обе партии. Определите максимальное количество поставок, которые можно принять в магазине, и минимально возможную длительность принятия последней поставки при этом условии.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество записей о поставках товаров.
Следующие N строк содержат пары чисел, обозначающих время начала и время завершения соответствующей поставки (в минутах от начала суток)
Запишите в ответе два числа: максимальное количество поставок, которые можно принять в магазине, и минимальная длительность принятия последней поставки.
Типовой пример организации данных во входном файле
5
10 150
100 110
133 170
145 180
120 130
При таких исходных данных можно принять максимум три поставки, например, поставки 2, 3 и 5. Принятие последней поставки по длительности в этом случае займёт 35 минут, если принять поставки 2, 4, 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов