Migrated from Lutece 2787 宝可梦

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

火箭队（日文︰ロケット団，英文︰Team Rocket）是个组织犯罪集团，主要活动地点为关都地区、城都地区和七之岛，目的为捕捉强大或稀有的宝可梦，以利用它们来夺取世界。

根据喵喵所说，火箭队是大型跨地区的上市公司，且给予手下完善的社会福利。

火箭队有 $n$ 种宝可梦，因为资金短缺，他们打算卖掉一些宝可梦。每一种宝可梦对于火箭队都有一个重要程度 $c$, 并且一只能卖出价格 $v$。第 $i$ 种宝可梦，火箭队拥有 $m_{i}$ 只。

火箭队希望卖出的宝可梦的重要程度之和不超过 $W$, 但他们也想要卖出尽可能多的钱。

为了防止世界被破坏。 为了维护世界的和平。 请你帮助火箭队选出一些宝可梦卖掉，使得他们能得到尽可能多的钱。

Input

第一行，两个整数 $n, W$ 。 下面 $n$ 行，每一行有三个整数 $v_{i}, c_{i}, m_{i} (1 \leq v_{i}, c_{i} \leq 4 \times 10^{4} )$ 。表示宝可梦能卖出的价格，重要程度，和数量

$n \leq \sum m_{i} \leq 10^{5}, 0 \leq W \leq 4 \times 10^{4}, 1 \leq n \leq 100$ 。

Output

一行，一个整数，表示火箭队能通过卖宝可梦得到的最多的钱。

Samples

3 10
3 3 3
4 4 2
5 5 1

10

Resources

2022 UESTC ICPC Training for Dynamic Programming