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]。求解将哪些宝石装入背包可使这些物品的容量总和不超过背包容量，且价值总和最大。

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

输出一个整数，即最大价值总和（保证不超过整型范围）。

对于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。