Description

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

Format

Input

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

接下来第 n+1 行，每行三个数：

a[i]（每棵树上的果子）,s[i]（这棵树上的所有果子的价格），c[i]（在 每棵树上花费的时间）

Output

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

Samples

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

13

Limitation

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

从第 i 棵树到第 j 树的时间忽略不计。

【（数据范围）】 n,k<=10000;a[i],s[i]<=maxint;