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

В парке развлечений есть $K$ аттракционов. Все аттракционы пронумерованы, начиная с единицы. Известно время, в которое каждый посетитель хочет начать свою поездку на аттракционе, и в какое время он закончит кататься на нём. Аттракцион считается свободным, если на нём никто не катается. Каждый посетитель должен выбрать свободный аттракцион с наименьшим номером. Если в момент прихода посетителя все аттракционы заняты, то посетитель уходит, не дожидаясь освобождения одной из них. Если некоторые посетители придут в парк одновременно, они будут кататься на одном и том же аттракционе вместе. Для того, чтобы остановить и запустить аттракцион заново, необходима 1 минута. Со следующей минуты следующие посетители могут воспользоваться аттракционом. Каждый посетитель за весь день может покататься только на одном аттракционе.

Определите, наибольшее количество посетителей, которые придут в парк и покатаются на аттракционах за 24 часа и номер аттракциона, на котором прокатится последний посетитель.

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

В первой строке входного файла находится два числа $K$ – количество аттракционов в парке развлечений и $N$ – количество посетителей, которые придут в этот парк (натуральные числа, не превышающее 2000). В следующих $N$ строках находятся два значения: минута прихода и минута, не раньше которой посетитель закончит кататься на аттракционе, отсчёт ведётся от начала суток (все числа неотрицательные, не превышающие 1440), для каждого посетителя – в отдельной строке.

Запишите в ответе два целых числа: сначала количество посетителей, которое сможет воспользоваться аттракционами в парке развлечений за 24 часа, затем номер аттракциона, на котором прокатится последний посетитель.

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

2 6

30 60

61 120

79 160

79 180

100 130

170 1440

При таких исходных данных 1-ый, 2-ой, 3-ий, 4-ый и 6-ой посетители смогут воспользоваться аттракционами. Последний турист сможет прокатиться на первом аттракционе.

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

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