시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 20 14 12 66.667%

문제

어떤 철도 노선이 두 역- A역과 B역-을 가지고 있다.


IMG_6360.JPG

열차들은 하루에 A역에서 B역으로, 혹은 B역에서 A역으로 여러 번 운행할 수 있다. 만약 열차가 A역에서 B역(혹은 B역에서 A역) 으로 도착하면, 다시 원래 역으로 돌아가기 위한 시간, 즉 회차시간을 필요로 한다. 예를 들어, 열차가 12:00에 도착했으며, 회차시간이 0분이라면, 열차는 12:00에 바로 역을 떠날 수 있다.

열차 시간표에는 A역과 B역 사이의 모든 열차의 출발시각과 도착시각이 적혀져 있다. 철도회사는 시간표대로 열차를 운행시키기 위해 A역과 B역에서 첫차로 출발시켜야 하는 차량의 갯수를 알아야 한다. 열차가 A역 혹은 B역을 출발하려면, 출발 준비가 된 차량이 존재해야 한다. 두 역 사이의 선로에는 대피선이 설치되어 있기 때문에 열차는 반드시 출발한 순서대로 도착할 필요가 없으며, 시간표에 적혀져 있는 열차 이외의 열차는 운행하지 않는다.

입력

첫 줄에는 테스트 케이스의 개수 N을 입력받는다.

각 테스트케이스는 여러 줄로 이루어져 있다, 첫 번째 줄은 회차 시간 T가 분으로 주어지며, 다음 줄에는 A에서 B로 가는 열차의 수인 NA, B에서 A로 가는 열차의 수 NB가 공백으로 구분되어서 입력된다. 다음 NA개의 줄에는 A에서 B로 이동하는 열차의 정보가 주어진다.

각 줄은 두 부분으로 나뉘며, HH:MM 포맷으로 출발 시간과 도착 시간이 주어진다. 각 열차의 출발 시각은 도착 시각보다 이르며, 모든 출발과 도착은 하루 안에 일어난다. 시간과 분은 모두 2자리이며, 빈 자리는 0으로 채우며, 24시간제이다(00:00~23:59)

NA개의 줄 뒤에는, B에서 A로 가는 열차의 출발시각과 도착 시각이 NB 줄만큼 주어진다.

제한

  • 1 ≤ N ≤ 100
  • 0 ≤ NANB ≤ 100
  • 0 ≤ T ≤ 60

출력

각 테스트케이스마다, Case #x: "뒤에 A역과 B역에서 출발시켜야 하는 차량의 수를 공백으로 구분하여 출력한다.

예제 입력

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

예제 출력

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

힌트