Cameron và Jamie là bạn đời lâu năm và vừa trở thành cha mẹ! Chăm sóc em bé tuy đầy hào hứng nhưng cũng không ít thử thách. Vì cả hai đều có tư duy khoa học, họ quyết định áp dụng một cách tiếp cận khoa học cho việc chăm con.

Cameron và Jamie đang xây dựng lịch sinh hoạt hằng ngày và cần quyết định ai sẽ là người chính chăm em bé tại mỗi thời điểm. Họ luôn là những người bạn đời bình đẳng và không muốn thay đổi điều đó, nên mỗi người phải phụ trách đúng 12 giờ (720 phút) mỗi ngày.

Cameron có \(A_C\) hoạt động và Jamie có \(A_J\) hoạt động khác mà họ cần hoặc muốn tự mình thực hiện. Các hoạt động này diễn ra vào cùng thời điểm mỗi ngày. Không hoạt động nào của Cameron chồng lấn hoạt động của Jamie, nên luôn có ít nhất một người rảnh để chăm em bé.

Họ muốn lập một lịch chăm em bé thỏa mãn:

• Thời gian chăm bé không được trùng với hoạt động đã định của chính người đó. Trong hoạt động của Cameron, Jamie phải chăm bé và ngược lại.
• Cameron và Jamie mỗi người được giao đúng 720 phút.
• Số lần đổi ca — số lần người phụ trách em bé chuyển từ người này sang người kia — phải nhỏ nhất.

Ví dụ, giả sử Jamie có một hoạt động buổi sáng từ 9 đến 10 giờ, còn Cameron có một hoạt động buổi chiều từ 14 đến 15 giờ. Một lịch hợp lệ nhưng chưa tối ưu là Jamie chăm từ nửa đêm đến 6 giờ và từ 12 đến 18 giờ, còn Cameron chăm từ 6 đến 12 giờ và từ 18 giờ đến nửa đêm. Lịch này thỏa hai điều kiện đầu và có bốn lần đổi ca: lúc nửa đêm, 6 giờ, 12 giờ và 18 giờ. Một lần đổi ca tại nửa đêm được tính đúng một lần, không phải không lần hay hai lần.

Phương án tốt hơn là Cameron chăm từ nửa đêm đến 12 giờ, Jamie chăm từ 12 giờ đến nửa đêm. Lịch này cũng thỏa hai điều kiện đầu nhưng chỉ dùng hai lần đổi ca, và đó là số nhỏ nhất có thể.

Với danh sách hoạt động của Cameron và Jamie, hãy tìm số lần đổi ca nhỏ nhất trong một lịch hằng ngày.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(A_C,A_J\), số hoạt động tương ứng của Cameron và Jamie. Tiếp theo có \(A_C+A_J\) dòng. \(A_C\) dòng đầu chứa \(C_i,D_i\): hoạt động thứ \(i\) của Cameron bắt đầu đúng \(C_i\) phút và kết thúc đúng \(D_i\) phút sau nửa đêm, kéo dài \(D_i-C_i\) phút. \(A_J\) dòng cuối chứa \(J_i,K_i\) với ý nghĩa tương tự cho Jamie. Không hoạt động nào kéo qua hai ngày; không có hai hoạt động chồng lấn, dù một hoạt động có thể kết thúc đúng lúc hoạt động khác bắt đầu và vẫn có thể đổi ca tại thời điểm đó.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lần đổi ca nhỏ nhất.

Ràng buộc

• \(1\le T\le100\).
• \(0\le C_i<D_i\le24\times60\) với mọi \(i\).
• \(0\le J_i<K_i\le24\times60\) với mọi \(i\).
• Hai khoảng bất kỳ trong \(\{[C_i,D_i)\}\cup\{[J_i,K_i)\}\) có giao rỗng. Các khoảng đóng bên trái và mở bên phải, nên hai khoảng liên tiếp sát nhau không chồng lấn.
• \(\sum_i(D_i-C_i)\le720\).
• \(\sum_i(K_i-J_i)\le720\).

Phân nhóm

Test Set 1 (Visible): \(0\le A_C,A_J\le2\) và \(1\le A_C+A_J\le2\).

Test Set 2 (Hidden): \(0\le A_C,A_J\le100\) và \(1\le A_C+A_J\le200\).

Đ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ụ

5
1 1
540 600
840 900
2 0
900 1260
180 540
1 1
1439 1440
0 1
2 2
0 1
1439 1440
1438 1439
1 2
3 4
0 10
1420 1440
90 100
550 600
900 950
100 150
1050 1400

Case #1: 2
Case #2: 4
Case #3: 2
Case #4: 4
Case #5: 6

Nguồn

Google Code Jam 2017, Vòng 1C, bài Parenting Partnering.

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