問題文

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

制約

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

入力

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

$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

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

出力例 1

3

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

入力例 2

1 1 10
10 10 10

出力例 2

-1

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