题目描述

一个旅行者有一个最多能装 $m$ 公斤的背包，现在有 $n$ 件物品，它们的重量分别是 $w_1, w_2, \dots, w_n$，它们的价值分别为 $c_1, c_2, \dots, c_n$。有的物品只可以取一次（$0$-$1$ 背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

第一行包含两个整数 $m, n$，分别表示背包容量和物品数量。

接下来 $n$ 行，每行包含三个整数 $w_i, c_i, p_i$，前两个整数分别表示每个物品的重量和价值，第三个整数若为 $0$，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数。

输出格式

输出一行一个整数，表示最大总价值。

10 3
2 1 0
3 3 1
4 5 4

11

提示

样例 1 说明

选择第一件物品 $1$ 件和第三件物品 $2$ 件。总重量为 $2 \times 1 + 4 \times 2 = 10$，总价值为 $1 \times 1 + 5 \times 2 = 11$。

数据规模与约定

对于全部的测试点，保证 $0 \leq m \leq 200$, $0 \leq n \leq 30$，并且对于每个物品，$w_i$ 和 $c_i$ 是非负整数，$p_i$ 是非负整数。