2959: 大采购
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Pluto 所在的学校终于放假了，Pluto 决定好好犒劳一下自己，所以当然要 去大采购了。 由于Pluto 力量有限，他只能搬运最多不超过 w个单位重量的物品。在超市 中，Pluto 一共看到了 n 样想买的东西，并且第 i 件商品每件重量为 ai，每件能 带给 Pluto 的愉悦程度为ci，其存货量为 mi。 现在，Pluto 想在能够搬走所买商品 的前提下，得到尽量大愉悦程度。你能帮帮他吗?
输入
第一行两个正整数n，w，含义见题面。 接下来n行，每行三个整数，第i+1 行的整数分别表示 ai，ci，mi。
输出
一行一个整数，表示Pluto 最大的愉悦程度。
样例输入 复制
4 15
5 6 4
3 4 3
1 1 5
2 3 3样例输出 复制
21提示
【数据规模和约定】 对于50%的数据，n ≤ 200，w ≤ 3000 ，mi ≤ 100。 对于100%的数据，n ≤ 500，w ≤ 10000 ，mi ≤ 1000，ai ≤ 100，ci ≤ 1000。