Bạn đã khám phá ra công thức ratatouille tối thượng, món ăn nổi tiếng của Pháp! Bạn biết cần những nguyên liệu nào và cần bao nhiêu gam mỗi nguyên liệu để làm một phần ratatouille. Nhưng bạn tin rằng ai cũng có thể nấu ăn, nên muốn chia sẻ công thức với cả thế giới... đồng thời kiếm thêm chút tiền!

Bạn đã đặt mua các gói nguyên liệu dễ vận chuyển. Mỗi gói chứa một lượng của đúng một nguyên liệu; các gói có thể có khối lượng khác nhau ngay cả khi chứa cùng nguyên liệu. Để tiện lợi, bạn đặt cùng một số lượng gói cho mỗi nguyên liệu.

Bạn muốn dùng các gói đó để tạo càng nhiều bộ kit ratatouille gửi khách hàng càng tốt. Một kit gồm đúng một gói của mỗi nguyên liệu và một nhãn ghi số nguyên phần ratatouille mà kit làm được. Vì không muốn bán thiếu cho khách hay lãng phí thức ăn, mỗi gói phải chứa từ 90% đến 110% (kể cả hai đầu) lượng nguyên liệu thật sự cần để làm số phần ghi trên nhãn.

Ví dụ, giả sử một phần ratatouille cần 500 g cà chua và 300 g hành. Bạn có một gói 900 g cà chua và một gói 660 g hành. Có thể ghép chúng thành kit làm hai phần. Hai phần cần 1000 g cà chua và 600 g hành; 900 g nằm trong khoảng \([90,110]\%\) của 1000 g, còn 660 g nằm trong khoảng \([90,110]\%\) của 600 g. Tuy nhiên, không thể ghi kit làm một hoặc ba phần, cũng không thể ghi 1.999 phần vì số phần phải là số nguyên.

Một số tập gói không bao giờ tạo được kit. Vẫn với công thức trên, nếu có gói 1500 g cà chua và 809 g hành thì không có số phần nào phù hợp. Ba phần cần 1500 g cà chua và 900 g hành, nhưng 809 g hành không nằm trong khoảng \([90,110]\%\); không số nguyên phần nào khác phù hợp.

Bạn muốn chia sẻ công thức với nhiều khách nhất nên cần tạo số kit hợp lệ lớn nhất. Mỗi gói chỉ được dùng trong nhiều nhất một kit. Lưu ý rằng bạn không cần tối đa hóa tổng số phần ratatouille được tạo. Hỏi có thể tạo nhiều nhất bao nhiêu kit?

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test gồm:

• Một dòng chứa hai số nguyên \(N\), số nguyên liệu, và \(P\), số gói của mỗi nguyên liệu.
• Một dòng chứa \(N\) số nguyên \(R_i\); số thứ \(i\) là số gam nguyên liệu thứ \(i\) cần cho một phần ratatouille.
• Tiếp theo là \(N\) dòng, mỗi dòng \(P\) số nguyên. Giá trị thứ \(j\) trên dòng thứ \(i\), \(Q_{ij}\), là số gam trong gói thứ \(j\) của nguyên liệu thứ \(i\).

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), còn y là số kit lớn nhất có thể tạo.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le R_i \le 10^6\) với mọi \(i\).
• \(1 \le Q_{ij} \le 10^6\) với mọi \(i,j\).

Phân nhóm

• Test Set 1 (Visible): \(1\le N\le2\), \(1\le P\le8\).
• Test Set 2 (Hidden): \(1\le N\le50\), \(1\le P\le50\), \(N\times P\le1000\).

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

6
2 1
500 300
900
660
2 1
500 300
1500
809
2 2
50 100
450 449
1100 1101
2 1
500 300
300
500
1 8
10
11 13 17 11 16 14 12 18
3 3
70 80 90
1260 1500 700
800 1440 1600
1700 1620 900

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

Nguồn

Google Code Jam 2017, Vòng 1A, bài Ratatouille.

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