B2173 多重背包

你有一个容量为 $V$ 的背包，以及 $n$ 种物品。第 $i$ 种物品的体积为 $w_i$，每件价值为 $val_i$，最多有 $c_i$ 件。 你可以选择每种物品若干件放入背包，但同一种物品选择的件数不能超过 $c_i$，且总容量不能超过 $V$。 请你求出在不超过背包容量的前提下，能获得的最大总价值。 >形式化题意：设第 $i$ 种物品选择 $x_i$ 件，则需要满足： >$$ >\sum_{i=1}^{n} x_i \cdot w_i \le V,\quad 0 \le x_i \le c_i >$$ >最大化目标： >$$ >\max \sum_{i=1}^{n} x_i \cdot val_i >$$

第一行两个整数 $n, V$，表示物品种类数与背包容量。 接下来 $n$ 行，每行三个整数 $w_i, val_i, c_i$，分别表示第 $i$ 种物品的体积、价值与最多件数。

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

### 样例解释 #1 一种可行的最优方案是： - 选第 1 种物品 $2$ 件：体积 $2\times 3=6$，价值 $2\times 4=8$ - 选第 3 种物品 $2$ 件：体积 $2\times 2=4$，价值 $2\times 3=6$ 总容量 $6+4=10 \le 10$，总价值 $8+6=14$，为最大值。 ### 数据范围 对于 $40\%$ 的数据，$1\le n \le 9$，$1\le V \le 1000$，$1\le c_i \le 5$。 对于 $100\%$ 的数据，$1\le n \le 500$，$1\le V \le 1000$，$1\le c_i \le 100$。