题目描述

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

输入格式

• 第一行为两个数字，分别是 V 和 N，其中 V 是背包的容量，N 是物品的种类数。
• 接下来的 N 行，每行描述一种物品的信息，包括该物品的占用空间 c[i]，价值 w[i] 和数量 n[i]。

输出格式

• 输出一个整数，表示将物品装入背包后的最大价值总和。

输入样例

8 2
2 100 4
4 100 2

输出样例

400

说明

• 在这个问题中，物品的数量是有限的，可以通过多重背包动态规划来求解。
• 题目要求在背包容量限制下选择哪些物品，使得物品的总价值最大。