Restoranlar
Müəyyən bir şəhərdə, eyni xüsusiyyətlərə malik N zalı olan restoranlar şəbəkəsi mövcuddur. Bayram öncəsi günündə korporativ tədbirlərin keçirilməsi üçün idarəyə K müraciət daxil olub. Hər bir müraciətdə tədbirin başlanğıc və bitmə vaxtı (saat 00:00-dan 23:59-a qədər) göstərilib. Hər bir tədbirin keçirilməsi üçün tam bir zal tələb olunur (hansı zalın olması fərq etmir). Tədbir bitdikdən sonra həmin zalda növbəti tədbirə hazırlıq üçün ən azı yarım saat vaxt lazımdır. Mümkün qədər çox müraciəti təmin etmək lazımdır. Əgər bütün müraciətləri təmin etmək mümkündürsə, bu zaman ən az sayda zal istifadə olunmalıdır.
Giriş verilənləri
Birinci sətirdə N və K (1 <= N, K <= 100) ədədləri verilir. Növbəti K sətirdə müraciətin başlanğıc və bitmə vaxtı SS:DD-SS:DD formatında verilir. Hər bir müraciətin bitmə vaxtı başlanğıc vaxtından ən azı bir dəqiqə çoxdur.
Çıxış verilənləri
Birinci sətirdə təmin edilən müraciətlərin sayı P və istifadə olunan zalların sayı Q ədədlərini göstərin. Növbəti P sətirdə hər biri üçün iki ədəd göstərin — müraciətin sıra nömrəsi (giriş faylında olduğu kimi) və zalın nömrəsi. Əgər məsələnin bir neçə həlli varsa, onlardan istənilən birini göstərin.