Mô tả vấn đề

Là một nhà trộn kem tài năng TranLoc đang lên kế hoạch để trộn ra một lượng nhỏ hóa chất C.
Để tạo ra hóa chất C, Lộc cần phải trộn hai hóa chất là A và B theo tỉ lệ thể tích là ~M_a:M_b~.
Thật may mắn là Lộc không có bất kì hóa chất nào trong tay. Nhưng vì đam mê anh ấy đã quyết định sang tiệm thuốc rần nhà để mua một số hóa chất Hiệu thuốc bán N loại hóa chất. Đối với mỗi loại hóa chất, có đúng một gói hóa chất đó trong kho. Gói hóa chất i chứa ~a_i~ grams hóa chất A và ~b_i~ grams hóa chất B, và được bán với ~c_i~ H3.2coin (đồng tiền quyền lực tại lab h3.2).
TranLoc sẽ mua một số gói này. Vì một lý do nào đó, anh ta phải sử dụng tất cả các gói đã mua để tạo ra chất C. Tìm số tiền tối thiểu cần thiết để tạo ra chất C. Nếu không thể tạo ra chất C bằng cách mua bất kỳ gói kết hợp nào ở hiệu thuốc, hãy in ra -1.

Sample Input 1

3 1 1
1 2 1
2 1 2
3 3 10

Sample Output 1

3

Số tiền chi tiêu sẽ được giảm thiểu khi mua gói hóa chất 1 và 2. Trong trường hợp này, hỗn hợp các hóa chất đã mua sẽ gồm 3 gam chất A và 3 gam chất B theo tỉ lệ mong muốn: 3: 3 = 1: 1. Tổng giá của các gói này là 3 H3.2coin.

Sample Input 2

1 1 10
10 10 10

Sample Output 2

-1

Tỷ lệ 1:10 của hai chất A và B không thể được thỏa mãn bằng cách mua bất kỳ sự kết hợp nào của các gói. Do đó, đầu ra phải là -1.