3.采购(buy.cpp)

【问题描述】

最近，伊萨去了一个古老的国家。在这么长的一段时间里，它曾经是世界上最富有和最强大的王国。因此，这个国家的人民仍然非常自豪，即使他们的国家不再那么富有了。该国家的商人是最固执的，他们每个人只卖了一件商品，价格是pi，但是如果你的钱少于qi，他们就会拒绝与你交易，而伊莎对每件商品的估价都是vi。 如果他有M单位的钱，伊莎能得到的最大价值是多少？

【输入格式】

输入文件名为 buy.in。

输入文件有包含多组数据，以文件结束标志为中止。

每组数据含：第一行：两个整数N，M（1≤N≤500，1≤M≤5000）开头，表示购买商品数量和初始金额。接着N行，每行包含三个数字Pi，Qi和Vi（1≤Pi≤Qi≤100，1≤Vi≤1000），它们的含义在描述中。

【输出格式】

输出文件名为buy.out。

N个整数分行输出，表示伊莎每次购买能得到的最大价值。

【输入输出样例 1】

del. in

2 10

10 15 10

5 10 5

3 10

5 10 5

3 5 6

2 7 3

del.out

5

11

【数据说明】

对于 100% 的数据，1 ≤ N ≤ 500, 1 ≤ M ≤ 5000,1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000

我们老师说01+贪心