/ FWOJ / 题库 /

Cindy的生日礼物5 - 二维背包

Cindy的生日礼物5 - 二维背包

描述

Cindy为了庆祝自己的生日,决定去商店给自己买一些礼物。

假设有商店里有\(N\)件礼物,每件礼物的价格为\(w_i\)元,价值为\(v_i\),质量为\(m_i\)kg,Cindy只带了\(V\)元钱,最多可以携带\(M\)kg的重物,每种礼物只有买一件和不买两种选择。请你计算出Cindy买下的礼物所能获得的最大价值和。

格式

输入格式

第一行为三个数,\(N\),\(V\)和\(M\)。
接下来的\(N\)行,每行三个数,第\(i+1\)行的三个数分别为\(w_i\),\(v_i\)和\(m_i\)。

\(1\leq N,V,M\leq 1000\)
\(1\leq w_i,v_i,m_i\leq 1000\)

输出格式

一行,所能获得的最大价值和。

样例

输入样例

4 5 6
3 1 2
4 2 4
5 3 4
6 4 5

输出样例

3

限制

内存256MB,时间1s。

信息

ID
1017
难度
9
分类
(无)
标签
递交数
1
已通过
1
通过率
100%
上传者