Coding is the closest thing we have to superpower !

2450 : 背包-多重背包问题
描述

设有N种物品,每种物品有一个重量及一个价值,且每种物品有若干件。同时有一个背包,最大载重量为M,今从N种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M,而价值的和为最大。

输入

第一行:两个整数,N(物品种数,N≤500)和M(背包容量,M≤6000);

第2..N+1行:每行三个整数W_i,C_i,S_i,表示每个物品的重量、价值和能放的最大数量。(W_i \le 100 ,C_i \le 1000 ,S_i \le 10

输出

一行:一个数,表示能获得的最大的价值。

样例

输入

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

输出

1040
标签
语言:
主题: