题目描述

Dolphin is planning to generate a small amount of a certain chemical substance C.
In order to generate the substance C, he must prepare a solution which is a mixture of two substances A and B in the ratio of $M_a:M_b$.
He does not have any stock of chemicals, however, so he will purchase some chemicals at a local pharmacy.
The pharmacy sells $N$ kinds of chemicals. For each kind of chemical, there is exactly one package of that chemical in stock.
The package of chemical $i$ contains $a_i$ grams of the substance A and $b_i$ grams of the substance B, and is sold for $c_i$ yen (the currency of Japan).
Dolphin will purchase some of these packages. For some reason, he must use all contents of the purchased packages to generate the substance C.
Find the minimum amount of money required to generate the substance C.
If it is not possible to generate the substance C by purchasing any combination of packages at the pharmacy, report that fact.

海豚计划生成少量某种化学物质 C。为了生成这种物质 C，他必须配制一种溶液，这种溶液是两种物质 A 和 B 按 $M_a:M_b$ 的比例混合而成的。 但他没有任何化学品库存，因此他将在当地药店购买一些化学品。
药店出售 $N$ 种化学药品。每种化学品都有一包库存。
这包化学品 $i$ 包含 $a_i$ 克 A 物质和 $b_i$ 克 B 物质，售价为 $c_i$ 日元（日本货币）。
海豚将购买其中一些包装。由于某种原因，他必须使用购买的包装中的所有物质来生成物质 C。求生成物质 C 所需的最小金额。如果在药房购买任何包装组合都不可能生成物质 C，请报告这一事实。

输入格式

输入内容按以下格式标准输入：

$N$ $M_a$ $M_b$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$:$
$a_N$ $b_N$ $c_N$

输出格式

打印生成物质 C 所需的最低金额。如果无法生成物质 C，则打印 -1。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #2

1 1 10
10 10 10

样例输出 #2

-1

样例 #3

样例输入 #3

样例输出 #3

说明

数据规模与约定

• $1≦N≦40$
• $1≦a_i,b_i≦10$
• $1≦c_i≦100$
• $1≦M_a,M_b≦10$
• $gcd(M_a,M_b)=1$
• $a_i$ 、 $b_i$ 、 $c_i$ 、 $M_a$ 和 $M_b$ 均为整数。

样例 $1$ 解释

通过购买化学品 $1$ 和 $2$ 的包装，可以最大限度地减少花费。
在这种情况下，所购化学品的混合物将含有 $3$ 克 A 物质和 $3$ 克 B 物质，二者的比例符合要求： $3:3=1:1$ .
这些包装的总价为 $3$ 日元。

样例 $1$ 解释

购买任何包装组合都无法满足 A 和 B 两种物质的比率 $1:10$ 。因此，输出结果应为 -1。