解题思路

本题中每类宝石都有数量限制，每颗宝石的价值和挖掘时间固定，要求在总时间 $T$ 内获得最大价值。

这是典型的多重背包问题。

对于第 $i$ 类宝石：

• 数量为 $X[i]$

题目内容

小明设计了一个挖掘宝石的小游戏。在游戏中有红宝石、蓝宝石、绿宝石等多种不同类型的宝石，当然也有昂贵的钻石。现在给出一个地图，在地图上有 $N$ 种不同的宝石。每一种宝石都有一颗或者多颗，同一种宝石每一颗的价值都是相同的。此外，每一种宝石都有一个挖掘时间。在给定的时间内，哪一个玩家挖掘的宝石的总价值最大就是游戏的赢家。

现在给出 $N$ 类不同宝石的数量以及每一类宝石中每一颗的价值和挖掘时间，并且给出一个总的游戏时间 $T$。在不考虑竞争对手的情况下，请问可以得到的最大价值是多少？

输入描述

单组输入。

第 $1$ 行输入一个正整数 $N$ 和一个正整数 $T$，分别表示宝石类型的数量和总游戏时间（分钟），两者之间用空格隔开。$N \le 100$，$T \le 1000$。

从第 $2$ 行到第 $N+1$ 行每一行三个正整数 $X[i], Y[i]$和$Z[i]$，分别表示第 $i$ 类宝石的数量、第 $i$ 类宝石中一颗宝石的价值和挖掘时间（分钟）。$X[i]$、$Y[i]$和$Z[i]$均不超过$100$。

输出描述

输出可以得到的最大价值。

样例1

输入

3 10
2 5 5
3 4 3
2 8 6

输出

12