← 返回题目列表

AtCoder · abc054_d

D. 混合实验

中文机器翻译题面 查看原题

分数: 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.