题目描述

イルカは、微量の物質Cを生成したいと考えています。
物質Cを生成するためには、タイプAの物質とタイプBの物質の混合比が $M_a:M_b$ となる溶液を用意する必要があります。
しかし、イルカは薬品を1つも持っていないため、薬局へ薬品を買いに行くことにしました。
薬局では、$N$ 種類の薬品を取り扱っており、各薬品 $i$ の在庫はちょうど1つです。
各薬品 $i$ は、タイプAの物質 $a_i$ グラム、タイプBの物質 $b_i$ グラム含んでおり、価格 $c_i$ 円で売られています。
イルカは、いくつかの薬品を薬局で買います。買った薬品は全て使わなければなりません。
物質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 を出力せよ。

题目大意

---

题目描述：

有 $N$ 个物体，第 $i$ 个物体含有 $a_i$ 质量的 A 元素 和 $b_i$ 质量的 B 元素，代价为 $c_i$ 。

问能否取若干个物体，使 A 元素与 B 元素质量之比为 $M_a : M_b$ ，并使代价最小。

---

输入格式:

第一行3个整数 $N ,M_a ,M_b$

下面 $N$ 行，每行3个整数 $a_i ,b_i ,c_i$

$N$ $M_a$ $M_b$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$

$:$
$a_N$ $b_N$ $c_N$

---

输出格式：

若能满足条件则输出 最小代价。

否则输出 -1

---

数据范围：

• $1\le N\le 40$

• $1\le a_i,b_i\le 10$

• $1\le c_i\le 100$

• $1\le M_a,M_b\le 10$

• $gcd(M_a,M_b)=1$

• 输入都为整数。

---

translated by @君のNOIP。

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

3

1 1 10
10 10 10

-1

提示

制約

• $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$は整数である。

Sample Explanation 1

最小予算となる組み合わせは、薬品 $1$ と薬品 $2$ を混合する場合です。 この場合、混合した溶液中に物質Aは $3$ グラム、物質Bは $3$ グラム含まれており、混合比は $3:3=1:1$ となって条件を満たします。 このときの合計価格は $3$ 円となります。

Sample Explanation 2

物質Aと物質Bの混合比が $1:10$ となる薬品の組み合わせはないので、-1を出力します。