AT_abc054_d [ABC054D] Mixing Experiment

[problemUrl]: https://atcoder.jp/contests/abc054/tasks/abc054_d イルカは、微量の物質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` を出力せよ。

### 制約 - $ 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`を出力します。