该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

小偷的背包2

题目背景

哎呀呀，终于进入海底城堡了，哈哈哈哈哈哈哈哈啊哈哈哈

题目描述

这天，小偷基德一不小心进入了海底城堡，在海底城堡，他发现了太多太多太多太多的宝物，以至于他都不知道该怎么来拿了，比较幸运的时，他今天开着潜水艇过来的，已知潜水艇可以装重量不超过m的物品，海底城堡里面一共有n种物品，每种物品都有特定的重量，价值和数量，问在不超过潜水艇装载重量的前提下，基德最多能拿出多少价值的物品

输入格式

第一行为二个整数n和m，分别表示宝物种数和潜水艇的最大载重 接下来n行每行三个整数，其中第i行第一个数表示第i类品重量 ，第二个整数表示一件该类物品的价值，第三个整数为该类物品数量。

输出格式

输出仅一个整数，表示在潜水艇不超载的情况下收集的宝物的最大价值。

样例 #1

样例输入 #1

4 20
3 9 3
5 9 1
9 4 2
8 1 3

样例输出 #1

36

提示

n≤∑m[i]（第i件物品的数量）≤2×10^5；

0 <m（潜水艇载重）≤4×10^4：1≤n(物品数量)<100。