Lily wants to make a special type of sandwich spread called "Savory Blend." To create this spread, she needs to mix two main ingredients, Ingredient A and Ingredient B, in a specific ratio of MA:MB.
Unfortunately, Lily doesn't have any of these ingredients in her kitchen, so she decides to go shopping at a local grocery store. The store offers N different varieties of pre-packaged ingredients. Each package contains a certain amount of Ingredient Ai grams and Ingredient Bigrams, and it's priced at Ci rupees.
Lily is determined to create her Savory Blend, and she commits to using all the ingredients she purchases. However, she wants to minimize her spending. Your task is to help Lily figure out the minimum amount of money she needs to spend to make her Savory Blend.
If it's impossible to achieve the desired blend with the available packages, return −1.
Input Format:
The first line of input contains 3 integers: N, Ma and Mb.
Then there are N lines describing each package. Each line contains 3 integers: Ai, Bi and Ci
Output Format:
Print the minimum amount of money required to make the Savory Blend. If it is not possible to make it, print −1 instead.
Constraints:
1≤N≤401≤Ai,Bi≤101≤Ci≤1001≤MA,MB≤10gcd(MA,MB)=1
The amount of money spent will be minimized by purchasing the 1st and 2nd packages.
In this case, the mixture of the purchased packages will contain 3 grams of the ingredient A and 3 grams of the ingredient B, which are in the desired ratio: 3:3=1:1.
The total price of these packages is 3 rupees.