炼制合金(Alloy Smelting)

题目描述

正在炼制一块合金，需要含有至少 a 克黄金与 b 克白银。

商店里有 n 块材料，第 i 块材料含有 x_i 克黄金与 y_i 克白银，且含有 w_i 克杂质。

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

输入格式

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

输出格式

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

样例输入 #1

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

样例输出 #1

20

数据范围

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

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐。

测试点分布