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

Проспект длиной $K$ метров освещён $N$ фонарями, стоящими вдоль него. Администрация города выяснила, что количество включённых фонарей избыточно для освещения всего проспекта – какие-то из них можно выключить, чтобы сэкономить на тратах электроэнергии, таким образом, что проспект все равно останется освещён полностью. Входной файл содержит данные о метках начала и конца отрезков, освещаемых фонарями.

Определите, какое максимальное количество фонарей можно выключить так, чтобы проспект остался освещён полностью, а также общее количество фонарей, которые, если их включить, освещают $K$-й метр проспекта.

Примечание. Начало проспекта определено 1-м метром, конец – $K$-м метром.

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

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

Запишите в ответе два числа: максимальное количество фонарей, которые можно выключить, и количество фонарей, которые, если их включить, освещают $K$-й метр проспекта.

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

5 50

1 30

28 50

20 40

1 10

15 50

При таких исходных данных можно выключить 3 фонаря: второй, третий и четвёртый. K-й метр может быть освещен 2 фонарями (если они включены): фонарь {28, 50} и фонарь {15, 50}. Ответ: 3 2.

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

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