Таксі#2083

Таксі

2 секунди

64 мегабайти

Дуже легка

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

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

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

Вхідні дані

Перший рядок вводу містить кількість замовлень $M$ ( $0 \leq M \leq 500$ 0 \leq M \leq 500). Наступні $M$ рядків описують замовлення, по одному в кожному рядку. Кожне замовлення включає час відправлення у форматі $hh : mm$ hh:mm (у діапазоні від $00 : 00$ 00:00 до $23 : 59$ 23:59), координати $(a, b)$ точки відправлення та координати $(c, d)$ пункту призначення. Всі координати — невід’ємні цілі числа, що не перевищують $200$ . Замовлення наведені у порядку зростання часу відправлення.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість таксі, необхідних для обслуговування всіх замовлень.

Приклади

Приклад 1