eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Таксі

Таксі

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Керувати службою таксі – зовсім не проста справа. Крім природної необхідності централізованого управління машинами для того, щоб обслуговувати замовлення по мері їх поступання і якомога швидше, потрібно також планувати поїздки для обслуговування тих клієнтів, які зробили замовлення наперед.

У вашому розпорядженні знаходиться список замовлень таксі на наступний день. Вам необхідно мінімізувати число машин таксі, необхідних для виконання усіх замовлень.

Для простоти будемо вважати, що план міста являє собою квадратну решеіку. Адресу у місті будемо позначати парою цілих чисел: x-координатою та y-координатою. Час, потрібний для того, щоб дістатись з точки з адресою (a, b) у точку (c, d), дорівнює |a-c|+|b-d| минут. Машина таксі може виконати чергове замовлення, або якщо це перше її замовлення за день, або вона встигає приїхати у пачаткову точку з попередньої кінцевої хоча б за хвилину до вказаного терміну. Зверніть увагу, що виконання деяких замовлень може звершитись після опівночі.

Вхідні дані

У першому рядку вхідного файлу записано число замовлень M (0M500). Наступні M рядків описують самі замовлення, по одному у рядку. Для кожного замовлення вказано час відправки у форматі hh:mm (в інтервалі з 00:00 до 23:59), координати (a, b) точки відправлення і координати (c, d) точки призначення. Усі координати у вхідному файлі невід'ємні і не перевищують 200. Замовлення записано впорядкованими по часу відправлення.

Вихідні дані

У вихідний файл виведіть єдине ціле число – мінімальну кількість машин таксі, необхідних для обслуговування усіх замовлень.

Приклад

Вхідні дані #1
12
00:04 46 12 45 36
01:59 45 36 36 35
02:00 46 46 36 36
02:01 1 1 2 2
02:10 2 2 101 1
02:11 47 29 40 100
05:34 94 75 20 48
05:35 49 85 20 39
06:13 13 31 31 13
07:23 48 10 48 40
12:21 12 21 13 31
13:57 45 37 39 40
Вихідні дані #1
4