Coming Home

John is going back home after a party. Currently, he is standing at a bus station and waiting for a bus to arrive. There is a timetable of arriving buses near the station. Besides this, John also knows the amount of time that is needed to get home with each bus. As he has only one ticket, there are no possibilities to change the bus somewhere in the middle of a trip in order to make it shorter. Can you help John calculate the minimal time that he needs to get home?

Input Specification

There is a number of test cases T (T ≤ 100) in the first line. Each test case contains the number of buses K (1 ≤ K ≤ 100) and the current time (in the format HH:MM). Each of the next K lines contains the arrival time of a bus (in the same format as the current time) and the travelling time Q (0 ≤ Q ≤ 1000) needed for John to get home (in minutes). Refer to the sample input as an example.

Output Specification

For each test case, output a single line containing “Case T: N”, where T is the test case number (starting from 1), and N is the minimal time (in minutes) needed for John to go back home.

Sample Input

1. 2
2. 1 18:00
3. 19:30 30
4. 2 18:00
5. 19:00 100
6. 20:00 30

download as text file

Output for Sample Input

1. Case 1: 120
2. Case 2: 150

download as text file