【题目描述】

一个旅行者有一个最多能装V𝑉公斤的背包，现在有n𝑛件物品，它们的重量分别是W1𝑊1，W2𝑊2，...,Wn𝑊𝑛，它们的价值分别为C1𝐶1,C2𝐶2...Cn𝐶𝑛。有的物品只可以取一次(0101背包)，有的物品可以取无限次（完全背包)，有的物品可以取的次数有一个上限(多重背包)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

【输入】

第一行:二个整数，M𝑀(背包容量，M≤200𝑀≤200)，N𝑁(物品数量，N≤30𝑁≤30);

第22..N+1𝑁+1行:每行三个整数Wi𝑊𝑖,Ci𝐶𝑖,Pi𝑃𝑖，前两个整数分别表示每个物品的重量，价值，第三个整数若为00，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数(P𝑃)。

【输出】

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

【输入样例】

10  3

2  1  0

3  3  1

4  5  4

【输出样例】

11

【提示】

【样例说明】

选第一件物品11件和第三件物品22件。