题目描述

小爱正在炼制一块合金，该合金需要 $a$ 克黄金与 $b$ 克白银。商店里有 $n$ 块材料，第 $i$ 块材料含有 $x_i$ 克黄金与 $y_i$ 克白银，且含有 $w_i$ 克杂质。

请问应该使用哪些材料，将它们炼制在一起，才能使得合金中黄金与白银含量不少于给定的要求，且杂质总和最小。所有材料均不可切割。

输入格式

• 第一行：三个整数：$n$，$a$ 与 $b$；
• 第二行到第 $n+1$ 行：第 $i+1$ 行有三个整数表示 $x_i$，$y_i$ 与 $w_i$
• 输入数据保证所要求的合金一定可以炼成。

输出格式

• 单个整数：表示炼制合金的最少杂质数量。

3 100 200
51 104 10
60 90 1
51 106 10

20

样例解释 1

选择第一块和第三块

数据范围

• $1\leq w_i\leq 10000$；
• $1\leq a,b\leq 300$；
• $1\leq x_i,y_i\leq 300$；
• 对于 $30\%$ 的数据，$1 \leq n \leq 10$；
• 对于 $60\%$ 的数据，$1 \leq n \leq 500$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 1000$。