Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа (в минутах от начала суток) и время, на которое пассажир сдает багаж (в минутах).
Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Если два пассажира приходят одновременно, приоритет будет у того, у кого время хранения багажа будет меньше.
Определите, сколько всего пассажиров не смогут оставить свой багаж в ячейках за 24 часа и общее время, в течение которого все ячейки будут заняты (без учета времени на разгрузку ячейки). Гарантируется, что все пассажиры, сдавшие багаж, заберут его в пределах 24 часов.
Входные данные
В первой строке входного файла находится число K – количество ячеек в камере хранения, во второй строке файла число N – количество пассажиров, сдающих багаж (натуральное число, не превышающее 1000). Каждая из следующих N строк содержит два натуральных числа: время сдачи багажа (не превышает 1440) и время хранения багажа (не превышает 1440).
Запишите в ответе два числа: количество пассажиров, которые не смогли воспользоваться камерой хранения и общее время, в течении которого все ячейки будут заняты.
Типовой пример организации данных во входном файле
2
5
30 30
40 60
59 1
61 59
1230 25
При таких исходных данных третий пассажир не сможет воспользоваться камерой хранения. Общее время, в течение которого все ячейки будут заняты — 57 минут.