#1734. 多重背包

多重背包

题目描述

张琪曼:"魔法石矿里每种魔法石的数量看起来是足够多,但其实每种魔法石的数量是 有限的。"

李旭琳:"所以我们需要改变装包策略啦。"

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

输入格式

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

输出格式

最大价值总和。

样例

输入样例

8 2
2 100 4
4 100 2

输出样例

400