Bạn sở hữu một nhà máy với hai dây chuyền lắp ráp. Dây chuyền thứ nhất sản xuất các loại hộp, và dây chuyền thứ hai sản xuất các loại đồ chơi để đặt vào những chiếc hộp đó. Mỗi loại hộp đi kèm với một loại đồ chơi tương ứng và ngược lại.

Ban đầu, bạn lấy một chiếc hộp từ dây chuyền thứ nhất và một món đồ chơi từ dây chuyền thứ hai. Sau đó, bạn có một vài lựa chọn:

• Bạn luôn có thể bỏ chiếc hộp đi và lấy chiếc hộp tiếp theo.
• Bạn luôn có thể bỏ món đồ chơi đi và lấy món đồ chơi tiếp theo.
• Nếu hộp và đồ chơi cùng loại, bạn có thể đặt đồ chơi vào hộp và gửi sản phẩm hoàn thiện đến khách hàng.

Bạn luôn lấy hộp theo đúng thứ tự mà chúng được tạo ra, và tương tự đối với đồ chơi. Bạn biết trước thứ tự các loại hộp và đồ chơi sẽ được sản xuất, và bạn muốn lập kế hoạch để gửi được nhiều đồ chơi đã đóng hộp nhất có thể cho khách hàng.

Cảnh báo: Hai dây chuyền lắp ráp tạo ra rất nhiều hộp và đồ chơi. Tuy nhiên, chúng có xu hướng tạo ra cùng một loại sản phẩm trong một khoảng thời gian dài trước khi chuyển sang loại khác.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, T. Tiếp theo là T bộ thử nghiệm.

Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa hai số nguyên N và M. Tiếp theo là một dòng chứa \(2 \times N\) số nguyên a₁, A₁, a₂, A₂, ..., aₙ, Aₙ, và một dòng khác chứa \(2 \times M\) số nguyên b₁, B₁, b₂, B₂, ..., bₘ, Bₘ.

Điều này có nghĩa là dây chuyền thứ nhất sẽ tạo ra a₁ chiếc hộp loại A₁, sau đó là a₂ chiếc hộp loại A₂, v.v., cho đến khi kết thúc với aₙ chiếc hộp loại Aₙ. Tương tự, dây chuyền thứ hai sẽ tạo ra b₁ món đồ chơi loại B₁, tiếp theo là b₂ món đồ chơi loại B₂, v.v., cho đến khi kết thúc với bₘ món đồ chơi loại Bₘ.

Một món đồ chơi có thể được khớp với một chiếc hộp khi và chỉ khi chúng có cùng số hiệu loại.

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy in ra một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số lượng đồ chơi đóng hộp tối đa mà bạn có thể gửi cho khách hàng.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le a_i, b_i \le 10^{16}\).
• \(1 \le A_i, B_i \le 100\).

Phân nhóm

• Tập thử nghiệm 1 (Visible): \(1 \le N \le 3, 1 \le M \le 100\).
• Tập thử nghiệm 2 (Hidden): \(1 \le N, M \le 100\).

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

4
3 3
10 1 20 2 25 3
10 2 30 3 20 1
3 5
10 1 6 2 10 1
5 1 3 2 10 1 3 2 5 1
3 5
10 1 6 2 10 1
5 1 6 2 10 1 6 2 5 1
1 1
5000000 10
5000000 100

Case #1: 35
Case #2: 20
Case #3: 21
Case #4: 0

Nguồn

Google Code Jam 2012, Vòng 1C, bài Box Factory.

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