Задание 26 ЕГЭ по информатике

Министерство транспорта планирует обновить всё дорожное покрытие на шоссе длиной $R$ километров. Часть работ была проведена ещё в прошлом году, потому дорожники, чтобы не выполнять двойную работу, определили вдоль шоссе отрезки дороги, которые уже отремонтированы, причем информацию о каких-то километрах занесли в реестр несколько раз. Каждый отрезок задаётся километровой меткой старта и конца. Назовём «непригодными» участками шоссе такие непрерывные отрезки, которые не отремонтированы и расположены между отремонтированными участками либо между краем шоссе и ближайшим отремонтированным участком.

Определите количество "непригодных" отрезков трассы, а также наибольшую длину среди отрезков трассы, которые были отремонтированы ещё в прошлом году.

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

В первой строке входного файла находятся два натуральных числа: $N$ ($N ≤ 10 000$) – количество отрезков, определенных дорожниками и $R$ ($R ≤ 5 000 000 000$) - длина шоссе. Следующие $N$ строк содержат пары чисел, обозначающих метку начала и метку конца текущего отрезка. Все числа натуральные, не превышают значение $R$.

Запишите в ответе два числа: количество "непригодных" отрезков и длину наибольшего из отремонтированных отрезков.

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

5 50

10 39

15 35

12 25

30 41

45 48

При таких исходных данных три участка являются "непригодными": 1-9, 42-44, 49-50. Длина наибольшего из уже отремонтированных участков равна 31 (10-41). Ответ: 3 31.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/11811_26.txt