В стоматологической клинике работает K специалистов. Все специалисты в базе данных сохранены по номерам от 1 до К.
В call-центр стоматологии звонят клиенты, желая записаться на прием ко врачу. В отчете предоставлена информация о звонках, которые происходили последовательно за определенный период времени. Известно время, на которое каждый клиент хочет записаться к специалисту, а также ID-номер специалиста, к которому хочет попасть клиент. При этом, согласно регламенту клиники, длительность любого приема составляет 30 минут. Администратор записывает клиента к специалисту, если на то время, в которое клиент желает пребывать на приёме, не назначено других, ранее сделанных записей. Но если запись к тому специалисту, к которому желает попасть клиент, невозможна, тогда администратор записывает клиента к специалисту с наименьшим ID-номером, среди всех тех, что свободны в рассматриваемое время. Специалисты могут принимать клиентов со следующей минуты после окончания приема предыдущего клиента. Если подходящих специалистов нет, то администратор просит прощения у клиента и сообщает, что он не может записать его.
Длительность рабочего дня стоматологической клиники составляет 840 минут. Последняя минута возможного начала приёма = 810.
Определите, сколько клиентов смогли записаться на прием, а также номер специалиста, к которому записался последний клиент.
Входные данные
В первой строке входного файла находится число N – количество клиентов, которые хотят записаться на прием (натуральное число, не превышающее 10000). Во второй строке находится число K – количество специалистов в стоматологической клинике. В следующих N строках находятся два значения: минута с которой клиент хочет записаться и номер специалиста, к которому клиент хочет записаться на прием. Отсчёт времени ведётся от начала рабочего дня стоматологии (все числа положительные, не превышающие 960). Данные в файле даны в том порядке, в котором клиенты звонили в call-центр стоматологии.
Запишите в ответе два целых числа: сначала количество клиентов, которые смогли записаться на прием, а затем номер специалиста, к которому записался последний клиент.
Типовой пример организации данных во входном файле
5
2
30 2
50 2
570 1
40 2
150 1
При таких исходных данных первый, второй, третий и пятый клиенты смогут записаться на прием. Последний клиент, которого смогли записать, был записан к первому специалисту.
Ответ для примера: 4 1.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
