В некотором городе есть сеть ресторанов, имеющая в общей сложности \textbf{N} практически одинаковых залов. Администрации поступило \textbf{K} заявок на проведение в предпраздничный день корпоративных мероприятий. В каждой заявке указано время начала и окончания (от \textbf{00:00} до \textbf{23:59}). Для проведения одного мероприятия нужен целиком один зал (какой конкретно, значения не имеет). После окончания мероприятия нужно не менее получаса для подготовки к следующему мероприятию в этом зале. Требуется удовлетворить как можно большее число заявок. Если можно удовлетворить все, то при этом следует использовать наименьшее число залов. \InputFile В первой строке содержатся числа \textbf{N} и \textbf{K} (\textbf{1} <= \textbf{N}\textit{, }\textbf{K} <= \textbf{100}). В каждой из следующих \textbf{K} строк содержится время начала и окончания заявки в формате \textbf{ЧЧ:ММ-ЧЧ:ММ}. Время окончания каждой заявки хотя бы на минуту больше времени её начала. \OutputFile В первой строке выведите два числа --- количество заявок \textbf{P}, которые удалось удовлетворить, и количество залов \textbf{Q}, которое пришлось задействовать. В каждой из следующих \textbf{P} строк выведите по два числа --- порядковый номер заявки (какой она стояла во входном файле) и номер зала. Если задача имеет несколько решений, то выведите любое из них.