№709641809
В автоматическом пункте выдачи заказов установлено несколько ячеек хранения. Клиент занимает одну ячейку с минуты прихода start по минуту ухода end включительно. После ухода ячейка становится доступной следующему клиенту только через одну минуту: её можно назначить не раньше минуты end+1.
Клиентов обслуживают в порядке возрастания времени прихода; если времена прихода совпадают - в порядке возрастания времени ухода. Каждому клиенту назначают свободную ячейку с наименьшим номером (ячейки пронумерованы начиная с 1). Если в момент прихода свободных ячеек нет, клиента не обслуживают.
Определите, сколько клиентов будет обслужено, и номер ячейки, назначенной последнему обслуженному клиенту.
Входные данные
В первой строке входного файла записаны два натуральных числа N и K - количество клиентов и количество ячеек (N не превышает 10 000, K не превышает 100). Каждая из следующих N строк содержит два натуральных числа start и end - минуту прихода и минуту ухода (start ≤ end, числа не превышают 1 000 000).
В ответе запишите два целых числа через вертикальную черту: сначала количество обслуженных клиентов, затем номер ячейки последнего обслуженного клиента.
Типовой пример организации данных во входном файле
5 2 1 4 2 3 3 6 5 7 8 10
При таких исходных данных будут обслужены 4 клиента из 5 (клиент с интервалом 3-6 не получит ячейку). Последнему обслуженному клиенту назначат ячейку 1. Ответ для примера: 4 | 1.
Типовой пример имеет иллюстративный характер. Чтобы выполнить это задание, используйте данные из прилагаемого файла.