Bạn vừa chuyển từ quê nhà lên một thành phố lớn! Bạn yêu mọi thứ ở môi trường mới, ngoại trừ đồ ăn. Quê hương của bạn cung cấp những món ăn ngon nhất trong vùng (được gọi là "đồ ăn chất lượng") và chắc chắn bạn sẽ nhớ nó.

May mắn thay, nhà hàng lớn nhất ở quê bạn có cung cấp dịch vụ giao hàng. Bạn có thể mua bất kỳ lượng thức ăn nào trong một lần giao. Có một khoản phí giao hàng cố định cho mỗi lần giao, bất kể lượng thức ăn được mua trong lần đó là bao nhiêu.

Nhà hàng này phục vụ nhiều loại thức ăn khác nhau. Mỗi loại thức ăn có hai thuộc tính: giá mỗi bữa ăn và thời gian hết hạn. Một "bữa ăn" sẽ nuôi sống bạn trong một ngày; một khi bữa ăn đã được ăn, nó không thể được ăn lại. Thời gian hết hạn của một loại thức ăn là số ngày tối đa mà thức ăn đó vẫn có thể ăn được, tính từ thời điểm bạn nhận được nó. Thời gian hết hạn bằng 0 có nghĩa là bạn phải ăn loại thức ăn đó ngay trong ngày giao hàng.

Trong một lần giao hàng, bạn có thể mua bao nhiêu loại thức ăn khác nhau tùy thích và bao nhiêu bữa ăn của mỗi loại tùy thích, miễn là bạn có đủ tiền. Lưu ý rằng nếu một loại thức ăn cụ thể có thời gian hết hạn là \(t\), việc đặt mua nhiều hơn \(t+1\) bữa ăn của loại đó trong một lần giao hàng là không hợp lý: ít nhất một bữa ăn sẽ bị hỏng trước khi bạn kịp ăn nó.

Nhà hàng này có dịch vụ giao hàng rất nhanh, vì vậy bạn sẽ nhận được tất cả thức ăn trong một lần giao vào cùng ngày bạn đặt mua, và bạn có thể ăn một số thức ăn ngay trong ngày hôm đó. Giao hàng là cách duy nhất để bạn nhận được đồ ăn chất lượng.

Cho một số tiền nhất định mà bạn có thể chi cho giá các bữa ăn và phí giao hàng, số ngày tối đa bạn có thể ăn đồ ăn chất lượng mỗi ngày là bao nhiêu?

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, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng ba số nguyên \(M\), \(F\) và \(N\), lần lượt biểu thị số tiền bạn có, phí giao hàng và số lượng loại thức ăn mà nhà hàng cung cấp. \(N\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(P_i\) và \(S_i\), lần lượt biểu thị giá mỗi bữa ăn và thời gian hết hạn của một loại thức ăn.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số ngày tối đa mà bạn có thể duy trì việc ăn ít nhất một bữa đồ ăn chất lượng mỗi ngày.

Ràng buộc

• \(1 \le T \le 50\).
• \(1 \le F \le M\).
• \(1 \le N \le 200\).
• \(1 \le P_i \le M\).

Phân nhóm

• Test set 1 (Visible Verdict):
• \(0 \le S_i \le 2,000,000\).
• \(1 \le M \le 2,000,000\).
• Test set 2 (Hidden Verdict):
• \(0 \le S_i \le 10^{18}\).
• \(1 \le M \le 10^{18}\).

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

3
32 5 2
5 0
10 2
10 10 1
10 10
10 1 1
1 5

Case #1: 3
Case #2: 0
Case #3: 8

Nguồn

Google Code Jam 2012, Vòng 3, bài Quality Food.

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