Hermione's Bag

Background

Special for beginners, ^_^

Problem Description

In Harry Potter and the Deathly Hallows, Harry Potter and his friends are on the run. Now there are many things to put into Hermione's bag, but the bag has a limited size, so we can only put in the most important items. Given the quantity, volume, and value of each kind of item, find the combination that maximizes the total value of the bag, and output this value. Hermione will thank you very much.

Input Format

The first line contains $2$ integers: the number of item kinds $n$ and the carrying volume of the bag $v$.

Lines $2$ to $n+1$ each contain $3$ integers: the quantity $m$, volume $w$, and value $s$ of the $i$-th kind of item.

Output Format

Output one integer: the maximum total value of items that can be taken.

Sample Input 1

2 10
3 4 3
2 2 5

Sample Output 1

13

Constraints

1s, 1024KiB for each test case.

Sample Explanation

Take one of the first kind and two of the second kind. The result is $3 \times 1 + 5 \times 2 = 13$.

Data Range

For $30\%$ of the data, $1 \le v \le 500$, $1 \le n \le 2000$, $1 \le m \le 10$, $1 \le w \le 20$, $1 \le s \le 100$.

For $100\%$ of the data, $1 \le v \le 500$, $1 \le n \le 2000$, $1 \le m \le 5000$, $1 \le w \le 20$, $1 \le s \le 100$.