1178: 采果子

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

第一行 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