Задача #825

(В. Петров) В парикмахерской работают K специалистов. У каждого специалиста есть свой номер, начиная с единицы. Администратору парикмахерской нужно записать N клиентов на следующий день. Известно время, в которое каждый клиент хочет прийти в парикмахерскую, и в какое время он хочет завершить прием. Администратор записывает клиента к специалисту с наименьшим номером, который свободен в тот промежуток, который нужен клиенту. Специалисты могут принимать клиентов со следующей минуты после предыдущего клиента. Если таких специалистов нет, то администратор просит прощения у клиента и сообщает, что он не может записать его.

Длительность рабочего дня парикмахерской составляет 600 минут.

Определите сколько клиентов смог записать администратор и номер специалиста, к которому записался предпоследний клиент.

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

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

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

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

2
5
30 60
40 50
20 100
40 60
10 30

При таких исходных данных первый, второй, и пятый клиенты смогут записаться на услугу. Предпоследний клиент, которого смогли записать, был записан ко второму специалисту.

Ответ для примера: 3 2.

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