分数: 400 点
问题陈述
海豚计划产生少量的某种化学物质C。
为了生成物质C,他必须制备一种溶液,该溶液是两种物质A和B的混合物,其比例为 M_a:M_b.
然而,他没有任何化学品库存,因此他将在当地药房购买一些化学品。
药店有卖 N 种化学品。对于每种化学品,都有一包该化学品的库存。
化学品包装 i 包含 a_i 克物质 A 和 b_i 克物质 B,售价为 c_i 日元(日本的货币)。
Dolphin 将购买其中一些包。由于某种原因,他必须使用购买的包裹中的所有内容来生成物质C。
找出生成物质 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.
在这种情况下,购买的化学品的混合物将包含 3 克物质 A 和 3 克物质 B,其比例为所需比例: 3:3=1:1.
这些套餐的总价为 3 日元。
示例输入 2
1 1 10 10 10 10
示例输出 2
-1
比率
购买任何包装组合都无法满足 A 和 B 两种物质的 1:10 。因此,输出应该是 -1.