A690. 多重背包
编程题
普及/提高-
知识点
题目描述
给定容量为 $m$的背包，以及$n$ 种物品。
每种物品有 $3$ 个属性，$w_i, v_i, cnt_i$ 分别表示第 $i$ 种物品的体积、价值、数量 。
请求出不超过背包容量的情况下可获得的最大价值。
每种物品有 $3$ 个属性，$w_i, v_i, cnt_i$ 分别表示第 $i$ 种物品的体积、价值、数量 。
请求出不超过背包容量的情况下可获得的最大价值。
输入格式
第一行输入两个整数 $m$ 和 $n$，分别表示背包的大小和物品的数量。
接来下 $n$ 行，每行三个整数 $w_i, v_i, cnt_i$，分别表示第 $i$ 种物品的体积、价值、数量。
接来下 $n$ 行，每行三个整数 $w_i, v_i, cnt_i$，分别表示第 $i$ 种物品的体积、价值、数量。
输出格式
一个整数表示最大价值
输入输出样例
输入 #1
10 1 5 100 1
输出 #1
100
说明/提示
$1 \leq n, m, w_i, v_i, cnt_i \leq 1000$