318007 - 多重背包

时限2s

现有N(1\leq N\leq 10^3)种宝石和一个容量为V(1\leq V\leq2\times10^5)的背包。第i种宝石最多有a[i] (1\leq a[i]\leq4\times10^5)件可用,每个占用的空间是v[i],价值是w[i]。求解将哪些宝石装入背包可使这些物品的容量总和不超过背包容量,且价值总和最大。

输入

输入第一行为两个数字,即VN。以下N行为每种物品的占用空间、价值和数量。

输出

输出一个整数,即最大价值总和(保证不超过整型范围)。

样例

输入

8 2 
2 100 4 
4 100 2

输出

400

提示

对于25\%的数据,N\leq10,V\leq200,1\leq \sum a[i]\leq50

对于50\%的数据,N\leq10^2,V\leq10^4,1\leq a[i]\leq4\times10^5

对于100\%的数据,1\leq N\leq 10^3,1\leq V\leq2\times10^5,1\leq a[i]\leq4\times10^5,1\leq v[i]\leq 4\times10^5,1\leq w[i]\leq 10^4

时间限制 2 秒
内存限制 128 MB
讨论 统计
上一题 下一题