#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。