This page is still under construction.

Parts of this page are still being built. What you see may change.

Taxi Cab Scheme

Time limit1sMemory limit128 MB

Summary
Given taxi rides sorted by departure time, find the fewest cabs needed so each ride is served, where a cab reaches the next pickup at least one minute early.
Level

Medium6 of 10

Topics
Graph, Sorting, Greedy
Solved
No attempts yet

Problem

Running a taxi company is not as simple as it may seem. Besides the obvious need to centrally dispatch cabs so that customers calling right now are picked up as quickly as possible, you also have to plan how to assign every ride that has been booked in advance. Given the list of all taxi rides booked for the next day, determine the minimum number of cabs needed to serve all of them.

To keep things simple, we model the city as a rectangular grid. An address is given by two integers: a street number and an avenue number. The time a taxi needs to travel from address (a,b)(a, b) to address (c,d)(c, d) is ∣a−c∣+∣b−d∣|a - c| + |b - d| minutes. A cab may take a booked ride if either it is the cab's first ride of the day, or the cab can travel from the destination of its previous ride to the source of the new ride and arrive at least one minute before the new ride's scheduled departure. Note that some rides may finish after midnight.

Input

The first line of input contains a single positive integer NN, the number of scenarios that follow. Each scenario starts with a line containing an integer MM (0<M<5000 < M < 500), the number of booked taxi rides. The next MM lines describe the rides. Each ride is given by a departure time in the format hh:mm (from 00:00 to 23:59), two integers aa bb for the coordinates of the source address, and two integers cc dd for the coordinates of the destination address. All coordinates are at least 0 and strictly less than 200. Within each scenario the booked rides are sorted by increasing departure time.

Output

For each scenario, output one line with the minimum number of cabs required to serve all of the booked taxi rides.

Examples5

  1. Example 1

    Input
    2
2
08:00 10 11 9 16
08:07 9 16 10 11
2
08:00 10 11 9 16
08:06 9 16 10 11
    Expected output
    1
2

  2. Example 2

    Input
    1
1
12:00 0 0 5 5
    Expected output
    1

  3. Example 3

    Input
    1
3
00:00 0 0 0 0
00:01 0 0 0 0
00:02 0 0 0 0
    Expected output
    1

  4. Example 4

    Input
    1
3
10:00 0 0 100 100
10:00 5 5 50 50
10:00 1 1 2 2
    Expected output
    3

  5. Example 5

    Input
    1
4
00:00 0 0 0 0
00:00 0 0 0 0
00:05 0 0 0 0
00:05 0 0 0 0
    Expected output
    2