A7076 | 混合实验

数据范围

• $1 \le N \le 40$；
• 对所有 $i$，有 $1 \le a_i \le 10$，$1 \le b_i \le 10$，$1 \le c_i \le 100$；
• $1 \le M_a \le 10$，$1 \le M_b \le 10$；
• $\gcd(M_a,M_b) = 1$；
• 输入中的所有数都是整数。



样例解释 1



这里 $N = 3$，$M_a = 1$，$M_b = 1$。

• 如果只选第 $1$ 个物体：$S_A = 1$，$S_B = 2$，比例为 $1:2$，不等于 $1:1$；
• 只选第 $2$ 个物体：$S_A = 2$，$S_B = 1$，比例为 $2:1$，不等于 $1:1$；
• 只选第 $3$ 个物体：$S_A = 3$，$S_B = 3$，比例为 $1:1$，代价为 $10$；
• 选第 $1$ 和第 $2$ 个物体：$S_A = 1 + 2 = 3$，$S_B = 2 + 1 = 3$，比例为 $1:1$，总代价为 $1 + 2 = 3$。

能满足比例 $1:1$ 的方案中，总代价最小的是选择第 $1$ 和第 $2$ 个物体，总代价为 $3$，所以答案是 $3$。



样例解释 2



这里只有 $1$ 个物体，$M_a = 1$，$M_b = 10$。

• 如果选这个物体，则 $S_A = 10$，$S_B = 10$，比例为 $1:1$，并不是 $1:10$；
• 如果一个物体也不选，则 $S_A = 0$，$S_B = 0$，比例没有意义，也不符合 $1:10$。