分数: 366 分
问题陈述
高桥是一家植物园的管理员。花园里包含 N 植物,每个编号为 1 to N.
各厂 i (1 \leq i \leq N)具有“观赏价值” A_i 和“抗旱性” B_i。观赏价值较高的植物对游客更具吸引力,而抗旱性较高的植物对缺水的适应能力更强。
预计今年夏季将出现强烈热浪,一些植物可能会因缺水而枯萎。具体来说,具有抗旱性的植物 B_i 至少是阈值 T 无需任何干预即可生存,但植物 如果不采取措施, B_i 小于 T 就会枯萎。
为了保护即将枯萎的植物,高桥决定在一些植物上安装灌溉设备。对于每株植物 i,他选择是否安装灌溉设备。灌溉设备可以安装在任何植物上(包括抗旱性至少为 T),也可以不安装。但每株植物最多可安装一台灌溉设备。在植物上安装灌溉设备 i 成本 C_i,安装了灌溉设备的植物无论其抗旱值如何都不会枯萎。
灌溉设备的总安装成本不得超过高桥的预算 M.
综上所述,植物 如果 i 满足以下任一(或两个)条件,则它会存活(不会枯萎):
- 厂区安装灌溉设备 i
- 其抗旱性 B_i 至少 T
不满足这两个条件的植物将会枯萎。请注意,即使同时满足两个条件,观赏价值也不会被计算两次。
高桥希望通过在预算范围内选择在哪些植物上安装灌溉设备来最大化幸存植物的总观赏价值 M.
找到观赏价值的最大可能总和 A_i 所有幸存的植物。
约束
- 1 \leq N \leq 100
- 1 \leq M \leq 10^4
- 1 \leq T \leq 10^9
- 1 \leq A_i \leq 10^6
- 1 \leq B_i \leq 10^9
- 1 \leq C_i \leq 10^4
- 所有输入值均为整数
输入
N M T A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
- 第一行包含植物数量 N,高桥的预算 M,以及抗旱阈值 T,用空格分隔。
- 的 i- 以下各项 N 线条蕴含观赏价值 A_i,抗旱性 B_i,以及灌溉设备安装成本 C_i 工厂 i,用空格分隔。
输出
在单行上输出存活植物的最大可能总观赏价值。
示例输入 1
3 100 50 80 30 60 50 60 40 30 40 50
示例输出 1
130
示例输入 2
5 200 100 100 50 80 200 150 120 150 80 90 50 200 30 80 90 70
示例输出 2
500
示例输入 3
10 500 1000 500 800 100 300 1200 80 450 500 150 200 2000 50 150 900 120 600 600 200 100 1500 40 350 400 180 250 1100 90 400 700 160
示例输出 3
2400