Taxi
Managing a taxi service is a challenging task. Beyond the need for centralized management to handle incoming orders swiftly, it's also crucial to plan trips for clients who have made reservations 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 x-coordinate and the y-coordinate. The time required to travel from the point (a, b) to the point (c, d) is calculated as |a-c| + |b-d| minutes. A taxi can take a new order either if it's the first order of the day or if it can reach the starting point from the previous endpoint at least one minute before the specified time. Note that some orders may be completed after midnight.
Input
The first line of the input contains the number of orders M (0 ≤ M ≤ 500). The following M lines describe the orders, one per line. Each order includes the departure time in the format hh:mm (ranging from 00:00 to 23:59), the coordinates (a, b) of the departure point, and the coordinates (c, d) of the destination point. All coordinates are non-negative and do not exceed 200. Orders are listed in order of their departure time.
Output
Output a single integer — the minimum number of taxis required to service all the orders.