配点 : $400$ 点

問題文

イルカは、微量の物質Cを生成したいと考えています。 物質Cを生成するためには、タイプAの物質とタイプBの物質の混合比が $M_a:M_b$ となる溶液を用意する必要があります。 しかし、イルカは薬品を1つも持っていないため、薬局へ薬品を買いに行くことにしました。 薬局では、$N$ 種類の薬品を取り扱っており、各薬品 $i$ の在庫はちょうど1つです。 各薬品 $i$ は、タイプAの物質 $a_i$ グラム、タイプBの物質 $b_i$ グラム含んでおり、価格 $c_i$ 円で売られています。 イルカは、いくつかの薬品を薬局で買います。買った薬品は全て使わなければなりません。 物質Cを生成するために、必要な最小予算を求めてください。 薬局で売られている薬品の組み合わせで、物質Cを生成できない場合はそれを報告してください。

制約

• $1 \leq N \leq 40$
• $1 \leq a_i,b_i \leq 10$
• $1 \leq c_i \leq 100$
• $1 \leq M_a,M_b \leq 10$
• $gcd(M_a,M_b)=1$
• $a_i$、$b_i$、$c_i$、$M_a$、$M_b$は整数である。

入力

入力は以下の形式で標準入力から与えられる。

$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 を出力せよ。

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

3

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

1 1 10
10 10 10

-1

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