题目描述

为了迎接班级的元旦晚会，班主任王老师特批了 $m$ 元请你帮忙采购物品，并给你一张清单，注明了王老师调研小卖部中出售的 $n$ 个待选物品的价格、价值（价值越高，同学们越喜欢）、以及最多能买到的数量。

请你编程计算出，$m$ 元最多能够采购到的物品的最大价值是多少？注意，$m$ 元不一定都要花完。

输入格式

第一行两个整数 $n,m$，其中 $n$ 代表清单中待选物品总数，$m$ 表示王老师的拨款金额。

接下来 $n$ 行，每行三个整数 $p,v,s$，分别表示第 $i$ 种物品的价格、价值和能够买的最大数量（购买数量范围 $0\sim s$）。

输出格式

一行一个整数，表示能够采购到的最大价值。

样例

3 50
10 60 2
20 100 2
30 120 1

260

提示

样例解释

共有 $3$ 种物品，预算 $50$ 元。

• 第 $1$ 种物品：价格 $10$ 元，价值 $60$，最多购买 $2$ 件；
• 第 $2$ 种物品：价格 $20$ 元，价值 $100$，最多购买 $2$ 件；
• 第 $3$ 种物品：价格 $30$ 元，价值 $120$，最多购买 $1$ 件。

最优采购方案为：购买 $2$ 件第 $2$ 种物品（$2\times 20=40$ 元，价值 $2\times 100=200$）和 $1$ 件第 $1$ 种物品（$10$ 元，价值 $60$），总花费恰好 $50$ 元，总价值 $200+60=260$。

其他组合的价值均不超过 $260$（例如购买第 $3$ 种和第 $2$ 种各 $1$ 件，花费 $50$ 元，价值 $120+100=220$），因此最大价值为 $260$。

数据范围

$1\le n\le 500$

$1\le m< 6000$

$1\le p,v\le 100$

$1\le s\le 10$

来源

动态规划 多重背包