Mixing Experiment

题目描述

Dolphin 计划生成少量的化学物质 C。
为了生成物质 C，他必须配制一种按 $M_a:M_b$ 比例混合的 A 与 B 溶液。
不过他没有任何化学品库存，所以他将到当地药房购买一些化学品。
药房出售 $N$ 种化学品。对于每一种化学品，库存中恰好有一包。
第 $i$ 种化学品的包装中含有 $a_i$ 克的 A 和 $b_i$ 克的 B，售价为 $c_i$ 日元（日本货币）。
Dolphin 将购买其中若干包。出于某种原因，他必须使用所购买包裹的全部内容来生成物质 C。
求生成物质 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$ 为整数。通过购买第 $1$ 包和第 $2$ 包可以使花费最少。
在这种情况下，所购化学品的混合物将包含 $3$ 克的 A 和 $3$ 克的 B，它们的比例为所需的比例：$3:3=1:1$.
这些包的总价为 $3$ 日元。
两种物质 A 和 B 的比例 $1:10$ 无法通过购买任意组合的包满足。因此输出应为 $-1$.

标签: AtCoder|abc054D

来源

AtCoder|abc054D