Train Timetable (Large)

Time limit5sMemory limit512 MB

Summary

Given each train's departure and arrival times plus a turnaround time, find the minimum trainsets needed at stations A and B to run the timetable.

Level: Medium4 of 10
Topics: Greedy, Sorting, Intervals
Solved: No attempts yet

Problem

A railway line has exactly two stations, A and B.

A train stopped at a station

Over one day trains run from A to B and from B to A several times. When a train arrives at B from A (or at A from B), it needs a turnaround time before it can leave again in the opposite direction. For example, if a train arrives at 12:00 and the turnaround time is 0 minutes, that train may leave at 12:00.

The timetable lists the departure time and the arrival time of every train between A and B. The railway company needs to know how many trainsets it has to place at A and at B before the day starts in order to run the timetable. A train can leave A or B only if a trainset that has finished its turnaround is standing at that station. The track between the two stations has passing loops, so trains do not have to arrive in the order they departed. No train other than those in the timetable runs.

Find the minimum number of trainsets that must be placed at A and at B.

Input

The first line contains the number of test cases $N$ .

Each test case spans several lines. The first line holds the turnaround time $T$ in minutes. The next line holds two integers separated by a space: $N_A$ , the number of trains from A to B, and $N_B$ , the number of trains from B to A. The next $N_A$ lines describe the trains from A to B, one per line.

Each of those lines holds a departure time and an arrival time in HH:MM format, separated by a space. Every train departs earlier than it arrives, and every departure and arrival happens within the same day. Hours and minutes are written with two digits each, padded with a leading zero, on a 24 hour clock from 00:00 to 23:59.

After the $N_A$ lines, $N_B$ lines give the departure and arrival times of the trains from B to A in the same format.

Limits

$1 \le N \le 100$
$0 \le N_A, N_B \le 100$
$0 \le T \le 60$

Output

For each test case print one line starting with Case #x: , followed by the number of trainsets that must be placed at A and the number that must be placed at B, separated by a space. Here $x$ is the test case number, counting from 1.

Examples7

Example 1

Input

2
5
3 2
09:00 12:00
10:00 13:00
11:00 12:30
12:02 15:00
09:00 10:30
2
2 0
09:00 09:01
12:00 12:02

Expected output

Case #1: 2 2
Case #2: 2 0

Example 2
Input
```
1
0
0 0
```
Expected output
```
Case #1: 0 0
```

Example 3

Input

1
0
2 1
09:00 10:00
11:00 12:00
10:00 11:00

Expected output

Case #1: 1 0

Example 4

Input

1
60
2 2
00:00 00:59
01:59 23:59
01:00 01:59
02:00 03:00

Expected output

Case #1: 2 1

Example 5

Input

1
10
1 3
06:00 06:30
05:00 05:30
05:31 05:40
07:00 07:10

Expected output

Case #1: 0 2

Example 6

Input

4
0
1 0
00:00 23:59
60
0 1
12:00 13:00
3
2 2
08:00 08:30
09:00 09:30
08:33 09:00
09:33 10:00
0
0 0

Expected output

Case #1: 1 0
Case #2: 0 1
Case #3: 2 0
Case #4: 0 0

Example 7

Input

2
30
1 1
10:00 10:30
11:00 11:30
31
1 1
10:00 10:30
11:00 11:30

Expected output

Case #1: 1 0
Case #2: 1 1