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

jk的回归

时间限制：1s

空间限制：256MB

Description

已知BTS（防弹少年团）黄金忙内田柾国7.14 solo回归震碎kpop，果吧为了阿米谋福利（冲中输），特别推出\(N\)种专辑+特典+各品牌随机物品组合，一只阿米省吃俭用终于攒下\(V\)元准备大力支持，但由于田柾国实在是太火了，为了让更多人买到甜酒果的第一份专辑,果吧对购买做出了限制条件，即第i种物品最多可以购买\(si\)件，每套礼包的价格是\(vi\),收藏价值为\(wi\),这只阿米想在储蓄金额内购买收藏价值最大的礼包，请输出最大价值

Input Format

第一行输入两个整数 \(N(1 \leq N \leq 1000)\) ， \(V(1 \leq  V \leq 2000)\)空格隔开，分别表示礼包种数和储蓄金额

以下 \(N\) 行,每行3个整数，vi,wi,si,\((1\leq vi,wi,si \leq 20000)\)分别表示第\(i\)种礼包的价格，收藏价值和购买限数

Output Format

输出一个整数，表示表示最大收藏价值

Data Range

• \((1 \leq N \leq 1000)\)
• \(V(1 \leq  V \leq 20000)\)
• \((1\leq vi,wi,si \leq 20000)\)

Input Example #1：

4 5
1 2 3
2 4 1
3 4 3
4 5 2

Output Example #1：

10