题目描述

有 $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$。

输出格式

若能满足条件则输出最小代价。否则输出 -1。

3 1 1
1 2 1
2 1 2
3 3 10

3

1 1 10
10 10 10

-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$。