[ABC054D] Mixing Experiment

------------ ## 题目描述： 有 $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。

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

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