Andy managed to qualify for the CCO once again! That is, the Canadian Chemistry Olympiad (imagine doing chemistry LUL).

The CCO is comprised of two parts, a written examination where participants are expected to tackle grueling theoretical problems, as well as a practical component for which demonstrating lab prowess is necessary for a better final result.

Andy's theoretical knowledge is unrivaled. Unfortunately, his practical skills are not.

Aspiring to qualify for the even more prestigious IChO, Andy has decided to polish up his fundamentals. Specifically, his ability to mix solutions together.

He has put together an assortment of ~N~ different solutions. Each is composed of ~2~ chemicals, the ~i^{th}~ solution is a mixture of ~a_i \text{ mL}~ of chemical A and ~b_i \text{ mL}~ of chemical B. As well, each solution comes with a cost of production ~c_i~.

Using any combination of his mixtures, Andy would like to create a solution in which the amounts of chemical A and B are in the ratio ~X : Y~. Each of the ~N~ solutions can only be used once. For all possible solutions with this ratio, he would like the one with the least total cost. Can you help Andy come up with the optimal solution?

Notice that sometimes Andy sets himself up for failure. In the case that making a solution with such a ratio is impossible, output ~-1~.

Input Specification

The first line contains three integers ~N~ ~(1 \le N \le 100)~, ~X~ and ~Y~ ~(1 \le X,Y \le 10^3),\ \gcd(X, Y) = 1~.

The next ~N~ lines will each contain three integers ~a_i,\ b_i,\ c_i~ ~(1 \le a_i, b_i \le 10^3),\ (1 \le c_i \le 10^6)~.

Output Specification

Output one integer, the minimum cost to make a solution with a ratio of ~X : Y~, or ~-1~ if it is not possible.

Subtasks

Subtask 1 [10%]

~N \le 20~

Subtask 2 [90%]

No further constraints.

Sample Input 1

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

Sample Output 1

5

Sample Explanation 1

It is optimal to use the second and third mixtures to yield a solution with ~3\text{ mL}~ of solution A and ~3\text{ mL}~ of solution B, resulting in a ratio of ~1:1~.

Sample Input 2

1 4 3
3 4 100000

Sample Output 2

-1