Celebration Party

Problem Background

Special for beginners, ^_^

Problem Description

To celebrate the class winning first place at the school sports meet, the homeroom teacher decided to hold a celebration party and allocated funds to buy prizes for the athletes. The goal is to buy prizes with the maximum total value within the allocated amount, to replenish their energy and stamina.

Input Format

The first line has two numbers $n\ (n\le 500),\ m\ (m\le 6000)$, where $n$ is the number of prize types to buy and $m$ is the allocated amount.

The next $n$ lines each have 3 numbers: the $i$-th line's $v_i,w_i,s_i$ represent the price, value (price and value are different concepts), and maximum purchasable quantity (you may buy from 0 to $s$ pieces) of the $i$-th prize type, where $v\le 100,\ w\le 1000,\ s\le 10$.

Output Format

One line with one number — the maximum total value obtainable from this purchase (note: value, not price).

Sample Input

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

Sample Output

1040

Constraints

$n\le 500$, $m\le 6000$, $v\le 100$, $w\le 1000$, $s\le 10$.

Time limit 1s, memory limit 1024KiB for each test case.