Ресторани
В деякому місті є мережа ресторанів, які мають загалом N практично однакових залів. Адміністрації поступило K заявок на проведення у передсвятковий день корпоративних заходів. У кожній заявці вказано час початку та закінчення (від 00:00 до 23:59). Для проведення одного заходу потрбно цілком одну залу (яку конкретно, значення не має). Після закінчення заходу потрібно не менше півгодини для підготовки до наступного заходу в цій залі. Потрібно задовільнити якомога більшу кількість заявок. Якщо можна задовільнити всі, то при цьому слід використовувати найменшу кількість залів.
Вхідні дані
У першому рядку містяться числа N і K (1 <= N, K <= 100). У кожному з наступних K рядків міститься час початку і завершення заявки у форматі ЧЧ:ММ-ЧЧ:ММ. Час заврешення кожної заявки хоча б на хвилину більше часу її початку.
Вихідні дані
У першому рядку виведіть два числа — кількість заявок P, які вдалось задовольнити, і кількість залів Q, які прийшлось задіяти. У кожному з наступних P рядків виведіть по два числа — порядковий номер заявки (якою вона стояла у вхідному файлі) і номер зали. Якщо задача має декілька розв'язків, то виведіть довільний з них.