Рабочее место участника

Чтобы спуститься по канатной дороге и сесть в поезд, требуется ровно 30 минут. Хотя вагончики канатной дороги приходят ежеминутно, вместимость их ограничена. Поэтому, когда заканчиваются рождественские каникулы и все гости горнолыжного курорта уезжают домой, на станции канатной дороги выстраивается длинная очередь, и многие туристы рискуют опоздать на свой поезд.

Напишите программу, которая определяет порядок посадки туристов в вагончики канатной дороги, минимизирующий количество опоздавших на поезд.

В первой строке входного файла содержатся два целых числа, разделенных пробелом – вместимость одного вагончика `N` (`1\ ≤\ N\ ≤\ 100`) и количество уезжающих групп туристов `K` (`1\ ≤\ K\ ≤\ 1000`). Далее следует `K` строк, каждая строка содержит время прихода группы на станцию канатной дороги в формате ЧЧ:ММ, время отхода их поезда в формате ЧЧ:ММ и количество человек в группе (целое число от 1 до 100), данные в строке разделены пробелами. Информация о группах упорядочена по времени их прихода. Время задано в пределах одних суток от 00:00 до 23:59. Разница между временем прихода группы и отхода их поезда не менее 30 минут.

В выходной файл вывести одно целое число – минимальное количество туристов, опоздавших на поезд.

2 3
08:00 08:35 3
08:00 08:31 5
08:03 08:35 5

1