Задача #2864

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

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

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

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

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

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

2
5
30 60
40 1110
59 60
61 120
1230 1440

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