题目描述

一个旅行者有一个最多能装 $M$ 公斤的背包，现在有 $n$ 件物品，它们的重量分别是 $W_1，W_2，...,W_n$，它们的价值分别是 $C_1,C_2,...,C_n$。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

输入格式

第一行：两个整数，$M$（背包容量，$M \le 200$），$N$（物品数量，$N \le 30$）； 第 $2 \dots N+1$ 行：每行三个整数 $W_i,C_i,P_i$，前两个整数分别表示每个物品的重量、价值，第三个整数若为 $0$，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数（$P_i$）。

输出格式

仅一行，一个数，表示最大总价值。

样例 #1

样例输入 #1

10 3
2 1 0
3 3 1
4 5 4

样例输出 #1

11

样例解释 #1

最优选择为：选第一件物品 $1$ 件（重量 $2$，价值 $1$）和第三件物品 $2$ 件（重量 $4 \times 2 = 8$，价值 $5 \times 2 = 10$）。总重量为 $2+8=10$，总价值为 $1+10=11$，符合背包容量限制，且为可获得的最大价值。

数据范围与提示

对于 $100\%$ 的数据，$1 \le M \le 200$，$1 \le N \le 30$，$1 \le W_i,C_i \le 100$，$0 \le P_i \le 100$。