eolymp
bolt
Try our new interface for solving problems
Məsələlər

Такси

Такси

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Управлять службой такси – совсем не простое дело. Помимо естественной необходимости централизованного управления машинами для того, чтобы обслуживать заказы по мере их поступления и как можно быстрее, нужно также планировать поездки для обслуживания тех клиентов, которые сделали заказы заранее.

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #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
Çıxış verilənləri #1
4