T182351 【例题】多重背包问题

设有 $n$ 种物品，每种物品有一个重量及一个价值。同时有一个背包，最大载重量为 $M$，现在从 $n$ 种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于 $M$，而价值的和为最大。

第一行有两个整数 $n$（$n \le 500$）和 $m$（$m \le 6000$），其中 $n$ 表示物品的总数，$m$ 表示最大载重量。 接下来 $n$ 行，每行 $3$ 个整数，$w_i$、$v_i$、$s_i$，分别表示第 $i$ 种奖品的重量、价值和该种物品的数量（放入 $0$ 件到 $s_i$ 件均可），其中 $w \le 100$，$v \le 1000$，$s \le 10$。

一行：一个整数，表示此次购买能获得的最大的价值。