#DP0103. 多重背包1

多重背包1

题目描述

nn 种物品要放到一个袋子里,袋子的总载重量为 mm,第 ii 种物品的重量为 wiw_i,把它放进袋子里会获得 viv_i 的收益,一共有 cic_i 个。问如何选择物品,使得在物品的总重量不超过 mm 的情况下,获得最大的收益?请求出最大收益。

输入格式

第一行两个整数 n,mn,m

接下来 nn 行,每行三个整数 wi,vi,liw_i,v_i,l_i

输出格式

一个整数,表示答案。

Samples

5 10
2 1 2
5 8 2
2 4 5
3 9 2
4 3 2
26

数据规模

对于所有数据保证 1n,m,vi,wi,ci1001≤n,m,v_i,w_i,c_i≤100