Problem1559--买奖品

1559: 买奖品

[Creator : ]
Time Limit : 1 sec  Memory Limit : 128 MB

Solved: 12Submit: 22Statistics

Description

CDUTCM的ACM小团队最近得到了一小波资金，于是SameLin队长准备拿来奖励训练辛苦的ACMers，他来到了购物商城，店员告诉SameLin这些奖品每种都有它的价格price， 价值value，还有每种奖品能够购买的数量quantity，由于资金有限，每个ACMer都想奖品的价值够高，所以SameLin希望用这笔资金买到价值最高的奖品，你能写个小程序帮他解决这个问题吗？

Input

输入第一行两个数，n(n<=500),m(m<=6000),店里所拥有的奖品种类和资金金额。

接下来N行，每行三个数，p , v , q 分别代表第i种奖品的价格和价值（和价格是不同概念）还有能够购买的数量（0...q）;其中（p<=100, v<=1000, q<=10）.

Output

输出一个数，占一行，表示SameLin能用这笔资金购买奖品获得价值的最大值。

Sample Input Copy 

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

Sample Output Copy 

1040

HINT

多重背包

Source/Category

 
Submit