【描述】

萌萌今天心情不错，于是走到郊外旅游。他边走边向四周望望，发现周围有许多果树。萌萌数出了这些果树上果子的个数，并且估了估每个的价格（真是个奇怪的人）。萌萌规定了一种采摘方案，就是对于第i棵树来说，它有a[i]个果子，且每个果子价格为s[i]，摘取时间为c[i]。那么，当你摘了第i个树上的果子后，后面你所选择去摘的果树上的果子数必须大于第i棵树上的果子数目，说白了就是一个上升序列,而且他不可以往回走。他只有k小时，那么，在萌萌所拥有的限定时间内，他想知道，这样摘取得最大值是多少？

【输入格式】

第一行2个数：n（表示这条路上的大树数），k（总共时间）

接下来第n+1行，每行三个数： a[i]（每棵树上的果子）,s[i]（这棵树上的所有果子的价格），c[i]（在每棵树上花费的时间）

【输出格式】

一个数，按这样方法摘取的最大值：m

【输入样例】

4 3
2 2 1
2 3 2
1 7 1
4 6 2

【输出样例】

13
（先摘第3棵树上的，再摘第4棵树上的）

【数据范围】

N,k<=10000;a[i],s[i]<=maxint;