← 返回题目列表

AtCoder · awc0019_d

D. 植物园保护计划

中文机器翻译题面 查看原题

分数: 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