题目背景

小 K 历经千辛万苦,终于解开了古老石碑上的谜题,找到了传说中王室的藏宝洞。洞里堆满了数不尽的珍宝,可他的采集车载重有限,装不下所有宝贝,只能忍痛放弃一部分。

题目描述

小 K 先对洞里的宝物做了清点:每种宝物可能有一件或多件,他也大致估出了每种宝物的单价。清点结果如下:藏宝洞里共有 $n$ 种宝物,第 $i$ 种宝物的价值为 $v_i$,重量为 $w_i$,数量为 $m_i$ 件。小 K 的采集车最大载重为 $W$。

请你帮他挑选一些宝物装进采集车,在总重量不超过载重的前提下,使装走宝物的价值总和最大。

输入格式

第一行为两个整数 $n$ 和 $W$,分别表示宝物种数和采集车的最大载重。

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$。

输出格式

输出仅一个整数,表示在采集车不超载的情况下收集的宝物的最大价值。

样例

4 20
3 9 3
5 9 1
9 4 2
8 1 3

47

提示

对于 $30\%$ 的数据,$1 \le m_i$,$\sum m_i\leq 10^4$,$0\le W\leq 10^3$,$1 \le w_i$,$v_i\leq 100$。

对于 $100\%$ 的数据,$1 \le m_i$,$\sum m_i \leq 10^5$,$0\le W\leq 4\times 10^4$,$1\leq n\leq 100$,$1 \le w_i$,$v_i\leq 1000$。