Ресторани#453
У місті є мережа ресторанів, що складається з майже однакових залів. Адміністрація отримала заявок на проведення корпоративних заходів напередодні свята. У кожній заявці вказані час початку та закінчення (від 00\!:\!00 до 23\!:\!59). Для проведення заходу необхідно надати цілий зал (який саме — не має значення). Після закінчення заходу потрібно щонайменше півгодини, щоб підготувати зал для наступного заходу. Потрібно розмістити максимальну можливу кількість заявок. Якщо можливо задовольнити всі заявки, то при цьому потрібно використати мінімальну можливу кількість залів.
У першому рядку задано числа та (1 \leq N, K \leq 100). Кожен з наступних рядків містить час початку та завершення заявки у форматі HH\!:\!MM-HH\!:\!MM. Час завершення у кожній заявці принаймні на одну хвилину пізніше за час початку.
У першому рядку виведіть два числа: кількість задоволених заявок і кількість використаних залів . У кожному з наступних рядків вкажіть два числа: номер заявки (у тому порядку, як у вхідному файлі) та номер залу. Якщо існує кілька можливих рішень, виведіть будь-яке з них.
Приклад 1