题目描述

有 $N$ 种物品和一个容量为 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件物品的体积为 $v_i$，价值为 $w_i$。

请你选择若干件物品装入背包，使所有物品的总体积不超过背包容量，并使物品的总价值最大。

请输出能够获得的最大总价值。

输入格式

第一行包含两个整数 $N$ 和 $V$，分别表示物品种数和背包容量。

接下来 $N$ 行，每行包含三个整数 $v_i$、$w_i$ 和 $s_i$，分别表示第 $i$ 种物品的体积、价值和最多可选数量。

输出格式

输出一个整数，表示在总体积不超过 $V$ 的条件下能够获得的最大总价值。

4 5
1 2 3
2 4 1
3 4 3
4 5 2

10

输入样例 #2

1 10
3 7 2

输出样例 #2

14

输入样例 #3

4 5
6 100 2
7 200 3
8 300 1
9 400 4

输出样例 #3

0

数据范围

对于 $30\%$ 的数据，$1 \le N,V \le 100$，$1 \le v_i,w_i,s_i \le 100$。

对于全部数据，$1 \le N \le 1000$，$1 \le V \le 2000$，$1 \le v_i,w_i,s_i \le 2000$。