Taxi#2083
Managing a taxi service is not an easy task. Besides the natural requirement for centralized management of cars to serve orders as they arrive as quickly as possible, it is also necessary to plan trips for those clients who have booked in advance.
You have a list of taxi orders for the next day. Your goal is to minimize the number of taxis needed to fulfill all these orders.
For simplicity, assume the city is laid out on a square grid. An address in the city is represented by a pair of integers: the -coordinate and the -coordinate. The time required to travel from point to point is |a - c| + |b - d| minutes. A taxi can take a new order if it is either the first order of the day for that taxi, or if it can reach the starting point from the previous endpoint at least one minute before the scheduled time. Note that some orders may be completed after midnight.
The first line of the input contains the number of orders (0 \leq M \leq 500). The next lines describe the orders, one per line. Each order includes the departure time in the format hh:mm (in the range from 00:00 to 23:59), the coordinates of the departure point, and the coordinates of the destination point. All coordinates are non-negative and do not exceed . Orders are listed in order of their departure time.
Output a single integer — the minimum number of taxis required to service all the orders.
Example 1