All Submissions


After his first ride on vintage train, Sheldon got so excited that he downloaded the schedule of trains from LA to Napa Valley and back. He soon figured out that a train can make multiple trips from LA to Napa Valley and then back to LA. When a train arrives at Napa Valley from LA (or arrives at LA from Napa Valley), it needs a C minutes before it is ready to take the return journey. Now he wants to know minimum number of vintage train starting from LA and Napa Valley.

For Example, lets say LA is point A and Napa Valley is point B.
A train starts form A at 12.02 and reaches B at 12.03.
If it takes 1 minute to start the return trip, then the train will be ready to start from B to A at 12.04.
If there is a train scheduled to start from B at or after 12.04 then this train can make the return trip and so a new train won't be required.

Input

First line contains no of test cases, T.
First line of each test case contains an integer C. Second line contains two integers, A and B, number of trains starting from LA and Napa Valley respectively. A + B lines follow.
Each lines contains two fields in format HH:MM (00:00 through 23:59), departure and arrival time for that trip. The departure time for each trip will be earlier than the arrival time. All arrivals and departures occur on the same day.
First A lines contains schedule of trains originating at LA. Next B lines contains schedule of trains originating at Napa Valley.
NOTE : Schedule is unsorted.

Output

For each test case, output one line containing minimum number of trains starting at LA and Napa Valley respectively.
Limits

Limits
T <= 10
0 <= C <= 60
0 <= A, B <= 10^5

Sample Input

2
1
2 2
12:02 12:03
12:06 12:09
12:10 12:12
12:04 12:07
5
4 2
00:12 00:18
00:00 00:10
00:00 00:10
00:01 00:06
00:07 00:13
00:02 00:11

Sample Output

2 0
4 2

Problem Setter : Pushkar Anand
Source : Google Code Jam, Qualification Round 2008

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0