题目描述

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

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

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

输入格式

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

输出格式

最大价值总和。

样例

输入样例

8 2
2 100 4
4 100 2

输出样例

400