#J3061. 跨年购物

跨年购物

题目描述

小紫在开一家小店,她的店只卖n件商品,每件商品都有一个独一无二的编号,编号从1~n。其中第i件商品的售价是ci RMB,当一位顾客购买这件商品后,其开心指数会增加hi。需要注意的是,每件商品的有效购买时间只有p分钟,当小紫在第ti分钟上架第i件商品时,顾客只能在ti分钟到ti+p-1分钟这个时间段内购买,超过有效时间小紫就会下架这件商品。另外,小紫规定对于每位顾客,每件商品最多只能购买一次。
为了开心地跨年,小蓝决定去小紫的小店购物。但是小蓝很忙,跨年前后空闲时间都很少,换句话说,小蓝只能在t分钟去小紫的小店,不能停留更长时间,所以小蓝只能购买所有在t分钟时上架的商品。
现在小蓝想知道如果她在a分钟去小紫的小店购物,预算是b RMB,那么怎样购物才能让她更加开心?最大开心指数是多少?

输入格式

输入共2+n行。
第1行有两个正整数n和p。其中n表示小紫小店里商品的数量,p表示商品的有效时间。
第2~n+1行,每行有3个正整数ci,hi,ti。其中ci表示第i件商品的价格,hi表示购买第i件商品后可以获得的开心指数,ti表示第i件商品在ti分钟上架。
第n+2行有两个正整数a和b。其中a表示小蓝在第a分钟去小紫的小店购物,b表示小蓝的购物预算是b RMB。

输出格式

输出本次购物小蓝可以达到的最大开心指数。
4 4
2 3 2
3 5 1
4 7 2
11 15 5
5 14
18

提示

样例解释:
已知在第5分钟上架的商品有1号、3号和4号,最优购物方案如下:小蓝花2 RMB买1号,此时开心指数为3,再花11 RMB买4号,此时开心指数为3+15=18,为最大值。
数据约定:
对于100%的数据:
1 <= n <= 4000
1 <= p <= 10000
1 <= ci, hi <= 4000
1 <= ti <= 10000
1 <= a <= 20000
1 <= b <= 4000