Souma Yukihira - Shokugeki no Souma!

Souma wants to make a small amount of a food ~F~.

To make the food ~F~, he needs to prepare a mixture of two ingredients ~X_1~ and ~X_2~, with a ratio of ~M_{X_1} : M_{X_2}~, both mass in grams.

Unfortunately, he has ran out of ingredients at his house. Therefore, he will go to the local grocery store to purchase the needed ingredients.

The grocery store sells ~N~ kinds of ingredients. For each ingredient, there is exactly one package of it in stock.

The package of ingredient ~i~ contains ~a_i~ grams of the ingredient ~X_{1_i}~ and ~b_i~ grams of the ingredient ~X_{2_i}~, sold for ~c_i~ dollars.

Souma intends to purchase some of these packages. He needs to use all of the purchased items to make his food ~F~.

Find the minimum amount of money required for him to make his desired food, ~F~.

If it is impossible to make his desired food, output -1.

Constraints

• ~1 \le N \le 40~
• ~1 \le a_i, b_i, M_{X_1}, M_{X_2} \le 10~
• ~1 \le c_i \le 100~

Input Specification

The first line of input will contain 3 space separated integers, ~N~, ~M_{X_1}~, and ~M_{X_2}~.

The next ~N~ lines of input will contain 3 space separated integers, ~a_i~, ~b_i~, and ~c_i~.

Sample Input 1

1 1 10
10 10 10

Sample Output 1

-1

Sample Input 2

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

Sample Output 2

3