304001 - 多重背包

现有N(N\le10)种物品和一个容量为V(0<V<200)的背包。第i种物品最多有n[i]件可用,每个占用的空间是c[i],价值是w[i]。全部物品总数不超过50。求解将哪些物品装入背包可使这些物品的容量总和不超过背包容量,且价值总和最大。

输入

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

输出

最大价值总和。

样例

输入

8 2
2 100 4
4 100 2

输出

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