Các cô cậu nhóc thường được lì xì tiền vào dịp tết. Sắn cũng vậy, mỗi dịp tết khi được lì xì tiền Sắn thường cho vào heo đất của mình để thực hiện các kế hoạch nhỏ.

Nhưng có một vấn đề lớn với heo đất. Không thể xác định được bên trong có bao nhiêu tiền. Vì vậy có thể đập con lợn thành từng mảnh chỉ để biết rằng có bao nhiêu tiền. Rõ ràng, Sắn muốn tránh tình trạng khó chịu này. Sắn chỉ muốn đập heo đất khi đến hạn. Khả năng duy nhất là cân con heo đất và thử đoán xem có bao nhiêu đồng xu bên trong.

Giả sử rằng chúng ta có thể xác định chính xác trọng lượng của con lợn và chúng ta biết trọng lượng của tất cả các đồng tiền xu. Sắn muốn biết tổng số tiền tối thiểu có thể có trong con heo đất này là bao nhiêu. Sắn cần bạn giúp đỡ.

Dữ liệu vào

• Đầu vào bao gồm các trường hợp thử nghiệm \(T\) \((T \le 30)\)
• Mỗi trường hợp thử nghiệm bắt đầu với một dòng chứa hai số nguyên \(E\) và \(F\). Chúng chỉ ra trọng lượng của một con lợn trống và con lợn chứa đầy tiền xu. Cả hai trọng lượng được tính bằng gam. Không có con lợn nào nặng hơn \(10\)kg
• Trên dòng thứ hai của mỗi trường hợp thử nghiệm, có một số nguyên \(N\) cho biết số lượng tiền khác nhau được sử dụng để bỏ heo. Theo sau là chính xác \(N\) dòng, mỗi dòng chỉ định một loại tiền. Các dòng này chứa hai số nguyên \(P\) và \(W\). \(P\) là giá trị của đồng xu tính theo đơn vị tiền tệ, \(W\) là trọng lượng tính bằng gam.

Dữ liệu ra

• In chính xác một dòng đầu ra cho mỗi trường hợp thử nghiệm. Mỗi dòng chứa một số nguyên là số tiền tối thiểu có trong heo đất. Nếu không thể xác định được số tiền tối thiểu này vì một lý do gì đó hãy in ra \(-1\)

Ràng buộc

• \(1 \le E,F,W \le 10000\)
• \(1 \le N \le 500\)
• \(1 \le P \le 50000\)

Input 1

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

Output 1

60
100
-1