Bir şəhərdə ümumilikdə n ədəd praktiki olaraq eyni zalı olan restoranlar şəbəkəsi var. Müdiriyyətə bayramdan bir gün əvvəl korporativ tədbirlər keçirmək üçün k ədəd sifariş daxil olmuşdur. Hər sifarişdə başlama və qurtarma vaxtı (00:00-dan 23:59-a qədər) göstərilmişdir. Bir tədbirin keçirilməsi üçün bütöv bir zal (hansı olmasının fərqi yoxdur) tələb olunur. Tədbir başa çatdıqdan sonra eyni zalda növbəti tədbirin keçirilməsinə hazırlıq üçün ən azı yarım saat gərəkdir. Mümkün olduqca daha çox sifarişi təmin etmək tələb olunur. Əgər hamısını yerinə yetirmək mümkündürsə, onda ən az sayda zaldan istifadə etmək lazımdır.

Giriş verilənləri

Giriş verilənlərinin birinci sətrində n və k (1 ≤ n, k ≤ 100) ədədləri yerləşir. Növbəti k sətrin hər birində SS:DD-SS:DD formatında uyğun sifarişin başlama və qurtarma vaxtı verilir. Hər sifarişin qurtarma vaxtı başlanğıcından ən azı bir dəqiqə böyükdür.

Çıxış verilənləri

Birinci sətirdə çıxışa iki ədəd – yerinə yetirilə bilmiş sifarişlərin sayı p və işə cəlb olunmuş zalların sayı q-nü verin.