В некотором городе есть сеть ресторанов, имеющая в
общей сложности N практически одинаковых залов. Администрации поступило K
заявок на проведение в предпраздничный день корпоративных мероприятий. В каждой
заявке указано время начала и окончания (от 00:00 до 23:59). Для проведения
одного мероприятия нужен целиком один зал (какой конкретно, значения не имеет).
После окончания мероприятия нужно не
менее получаса для подготовки к следующему мероприятию в этом зале. Требуется
удовлетворить как можно большее число заявок. Если можно удовлетворить все, то
при этом следует использовать наименьшее число залов.
В первой строке входного файла содержатся
числа N и K (1 £ N, K £ 100). В
каждой из следующих K строк содержится время начала и окончания заявки в
формате ЧЧ:ММ-ЧЧ:ММ. Время окончания каждой заявки хотя бы на минуту
больше времени её начала.
В первой строке выходного файла выведите
два числа — количество заявок P, которые удалось удовлетворить, и
количество залов Q, которое пришлось задействовать. В каждой из
следующих P строк выведите по два числа — порядковый номер заявки
(какой она стояла во входном файле) и номер зала. Если задача имеет несколько
решений, то выведите любое из них.
Пример
|
Входные данные
|
Выходные данные
|
|
3
4
17:00-20:00
18:00-21:00
15:00-17:30
21:00-23:30
|
4
2
1
1
2
2
3
2
4
1
|
