Description

At last, the millennium-old puzzle was solved. Xiao FF found the royal treasure vault, filled with countless priceless treasures.

Xiao FF is about to get rich. However, there are simply too many treasures, and his collection cart cannot hold them all. He has to give up some of them.

Xiao FF sorted the treasures in the cave and found that each type of treasure has one or more copies. He roughly estimated the value of each type and then began the selection: the collection cart has a maximum load of $W$. There are $n$ types of treasures in total. For each type, the value is $v_i$, the weight is $w_i$, and there are $m_i$ copies. Under the constraint that the cart does not exceed its load, Xiao FF wants to choose some treasures to put into the cart so that the total value is maximized.

Input Format

The first line contains two integers $n$ and $W$, representing the number of types of treasures and the maximum load of the collection cart.

The next $n$ lines each contain three integers $v_i, w_i, m_i$.

Output Format

Output a single integer, the maximum total value of treasures that can be collected without exceeding the cart’s load.

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

47

Hint

For $30\%$ of the testdata, $1 \le m_i$，$\sum m_i\leq 10^4$，$0\le W\leq 10^3$.

For $100\%$ of the testdata, $1 \le m_i$，$\sum m_i \leq 10^5$，$0\le W\leq 4\times 10^4$，$1\leq n\le 100$.

Translated by ChatGPT 5