题目描述

张老师准备环游世界，出发之前要做的最重要的事情，当然是整理自己的背包啦。张老师有一个容积为 $m$ 的背包 ，有 $n$ 个物品作为放入背包的待选物品 ，每样东西都有自己的价值 $W_i$ 和体积 $V_i$ ，第 $i$ 个物品有 $N_i$ 个 （$N_i=0$ 时表示有无限多个），请你编程帮助张老师计算，他的背包能够存入的最大价值是多少？

输入格式

第 1 行有 2 个整数 $n,m$，表示物品的种类和背包的容积；

第 $2-N+1$ 行，每行有 3 个整数$V_i，W_i，P_i$，分别表示每个物品的体积、价值、个数。$（0 \le V_i \le 5000,W_i \le 5000, P_i \le 1000）$

输出格式

一个整数，表示能够存入背包的最大价值。

样例

5 50
1 1 50
2 4 3
48 49 1
1 51 1
3 3 3

106

数据规模

• 30%数据满足 $1 \le m,n \le 1000$
• 100%数据满足 $1 \le m,n \le 10000$