Magry有个好朋友Ricardo快要过生日了。Ricardo突然想到可以借生日坑蒙拐骗点东西出来，于是就找了Magry要他买零食当生日礼物。
Magry手上没那么多钱，不过想了想还是上了天猫超市搜了一波，被那么多吃的看的眼花缭乱头晕目眩不知所措，因为Ricardo只有一个要求，那就是东西尽量好吃，而且还不要有Ricardo不喜欢的东西。。。
Magry已经知道的是：卖的零食总共有n种，不过比较坑爹的是一种零食一个用户限购一件；每种商品的价格为x元，好吃程度为w。另外，Magry已经知道在那些零食中有一部分是Ricardo不喜欢的（也许是忌口，总之这个和零食的好吃程度毫无关联，甚至对于一部分好吃程度为0甚至是负数的黑暗料理Ricardo也很有可能喜欢吃）。然后，Magry身上总共只有k元。
现在，Magry想要的是：如何确定购买方案使得在Magry手上的k元不会被透支（即商品总额不大于k元）的情况下买到总的好吃程度最高并且没有Ricardo不喜欢的零食呢？
时间很急很关键，亲们快帮他一把！(另请注意Hint很关键一定要看～)
多组测试数据。
每组数据第一行为一个数，为商品种类数n，$0 \leq n \leq 10000$
接下来n行，每行3个整数x,w,t，每行分别表示一种商品，x代表商品价格，w代表东西的好吃程度，t表示Ricardo喜不喜欢这个东西，1表示喜欢，0表示不喜欢。其中$1 \leq x \leq 1000$，w在int范围内。
还有最后一行，一个数，k，表示Magry手头的钱。$0 \leq k \leq 100000$
对于每组数据，输出一行，一个数，表示Magry在手头的k元不被透支的情况下所购商品的最大好吃程度。
2
3 61 1
7 101 0
100
1
10 1 0
261
0作为生日礼物，Magry可是不情愿买好吃程度为0或者负值的黑暗料理的。
所以，碰见满满的零食列表，面对某些情况，Magry只好什么都不买，并且对Ricardo说：“很抱歉，我没法给你买合适的零食了。”
本题为防止TLE到停不下来，建议如下：