题目描述

小 $y$ 请你帮忙采购用于乔斯币兑换的奖品，现在给你 $m$ 元钱并附带一张清单，注明了 小 $y$ 调研小卖部中出售的 $n$ 种待选物品的价格、价值、以及最多能买到的数量。

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

输入格式

第一行两个整数 $n,m$，$n$ 表示清单中待选物品总数， $m$ 表示所有金额。

接下来 $n$ 行，每行3个整数 $v,w,s$ 分别表示第 $i$ 种物品的价格、价值和能够买的最大数量。

$n≤500,m≤8000$

$1≤(v,w)≤1000,0≤s≤10$

输出格式

5 1000
80 20 4
40 30 6
20 20 1
40 50 9
30 50 7

1040

提示