题目描述

张老师准备环游世界，出发之前要做的最重要的事情，当然是整理自己的背包。

张老师有一个容积为 $M$ 的背包，有 $N$ 种物品作为放入背包的待选物品。第 $i$ 种物品的体积为 $V_i$，价值为 $W_i$，数量为 $P_i$。当 $P_i=0$ 时，表示这种物品有无限多个；否则表示这种物品最多可以选择 $P_i$ 个。

请你帮助张老师计算，在背包容积不超过 $M$ 的情况下，能够获得的最大价值是多少。

输入格式

第一行输入两个整数 $N,M$，分别表示物品种类数和背包容积。

接下来 $N$ 行，每行三个整数 $V_i,W_i,P_i$，分别表示第 $i$ 种物品的体积、价值和数量。

输出格式

输出一个整数，表示能够获得的最大价值。

样例

3 10
2 3 0
3 4 1
4 5 2

15

样例解释

第 $1$ 种物品数量无限，选择 $5$ 个第 $1$ 种物品，体积为 $2\times5=10$，价值为 $3\times5=15$，可以获得最大价值 $15$。

数据范围

对于 $100\%$ 的数据，$1 \le N,M \le 10000$，$1 \le V_i,W_i \le 5000$，$0 \le P_i \le 1000$。

来源

动态规划 / 混合背包