问题描述

Dolphin 打算生成一种化学物质 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。