Một tuyến tàu hỏa có hai ga A và B. Các đoàn tàu có thể thực hiện các chuyến đi từ A đến B hoặc từ B đến A nhiều lần trong ngày. Khi một đoàn tàu đến B từ A (hoặc đến A từ B), nó cần một khoảng thời gian nhất định trước khi sẵn sàng thực hiện hành trình ngược lại - đây được gọi là thời gian quay đầu (turnaround time). Ví dụ, nếu một đoàn tàu đến lúc 12:00 và thời gian quay đầu là 0 phút, nó có thể khởi hành ngay lập tức lúc 12:00.

Một lịch trình tàu hỏa quy định thời gian khởi hành và thời gian đến của tất cả các chuyến đi giữa A và B. Công ty tàu hỏa cần biết cần bao nhiêu đoàn tàu để bắt đầu ngày mới tại A và B nhằm đảm bảo lịch trình hoạt động thông suốt: bất cứ khi nào một đoàn tàu được lịch trình cho phép rời A hoặc B, phải thực sự có một đoàn tàu ở đó sẵn sàng khởi hành. Có các đoạn tránh trên đường ray, vì vậy các đoàn tàu không nhất thiết phải đến theo đúng thứ tự mà chúng đã rời đi. Các đoàn tàu không được phép thực hiện các chuyến đi không xuất hiện trong lịch trình.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(N\). Tiếp theo là \(N\) bộ test.

Mỗi bộ test bao gồm nhiều dòng. Dòng đầu tiên là thời gian quay đầu, \(T\), tính bằng phút. Dòng tiếp theo có hai số, \(NA\) và \(NB\). \(NA\) là số chuyến đi từ A đến B, và \(NB\) là số chuyến đi từ B đến A. Sau đó là \(NA\) dòng cung cấp chi tiết các chuyến đi từ A đến B.

Mỗi dòng chứa hai trường, cho biết thời gian khởi hành và thời gian đến theo định dạng HH:MM cho chuyến đi đó. Thời gian khởi hành của mỗi chuyến đi sẽ sớm hơn thời gian đến. Tất cả các lần đến và đi đều xảy ra trong cùng một ngày. Các chuyến đi có thể xuất hiện theo bất kỳ thứ tự nào - chúng không nhất thiết phải được sắp xếp theo thời gian. Các giá trị giờ và phút đều có hai chữ số, được đệm số 0 và sử dụng hệ giờ 24 tiếng (00:00 đến 23:59).

Sau \(NA\) dòng này, có \(NB\) dòng cung cấp thời gian khởi hành và thời gian đến cho các chuyến đi từ B đến A.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(x\): " theo sau là số lượng đoàn tàu phải bắt đầu tại A và số lượng đoàn tàu phải bắt đầu tại B.

Ràng buộc

• \(1 \le N \le 100\).
• \(0 \le T \le 60\).

Phân nhóm

• Small dataset (Test set 1 - Visible): \(1 \le N \le 20\); \(0 \le NA, NB \le 20\); \(0 \le T \le 5\).
• Large dataset (Test set 2 - Hidden): \(1 \le N \le 100\); \(0 \le NA, NB \le 100\); \(0 \le T \le 60\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2008, Vòng loại, bài Train Timetable.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.