题目描述

你有一个容量为 $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$ 种物品的体积、价值与最多件数。

输出格式

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

3 10
3 4 2
4 5 3
2 3 4

14

提示

样例解释 #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$。