#BPV01. 旧录音修复计划
旧录音修复计划
旧录音修复计划
学校准备修复一批旧录音。第 i 段录音需要先用 a_i 分钟清除杂音,再用 b_i 分钟修复缺损,完成后能获得 v_i 点资料价值。
每段录音最多修复一次。只有两步都完成才获得价值,不能只完成其中一步。不同录音的修复互不影响,所有工作依次进行。
修复室今天最多开放 T 分钟,可以提前结束,也可以不修复任何录音。请问今天最多能获得多少点资料价值?
输入格式
第一行两个整数 N、T。
接下来 N 行,每行三个整数 a_i、b_i、v_i,含义如题目所述。
输出格式
输出一个整数,表示题目所求的最大值。
数据范围
1 ≤ N ≤ 100,1 ≤ T ≤ 1000;1 ≤ a_i,b_i ≤ 1000,1 ≤ v_i ≤ 10000。
样例
输入
4 12
2 2 7
3 2 9
1 2 5
5 3 12
输出
21
说明
选择第 1、2、3 段,总用时为 4+5+3=12 分钟,总价值为 7+9+5=21。