说明

你有一个容量为 $V$ 的背包，以及 $n$ 种物品。第 $i$ 种物品的体积为 $w_i$，每件价值为 $v_i$，最多有 $c_i$ 件。

你可以选择每种物品若干件放入背包，但同一种物品选择的件数不能超过 $c_i$，且总容量不能超过 $V$。

请你求出在不超过背包容量的前提下，能获得的最大总价值。

输入格式

第一行两个整数 $n, V$，表示物品种类数与背包容量。

接下来 $n$ 行，每行三个整数 $w_i, v_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$，为最大值。

数据范围

对于 $30\%$ 的数据，$1\le n \le 9$，$1\le V \le 1000$，$1\le w_i,v_i,c_i\le 10$。

对于 $80\%$ 的数据，$1\le n \le 500$，$1\le V \le 10000$，$1\le w_i,v_i,c_i\le 1000$。

对于 $100\%$ 的数据，$1\le n \le 5000$，$1\le V \le 10000$，$1\le w_i,v_i\le 100,1\le c_i\le 1000$。