Description

To celebrate the class's achievement of ranking first in the school sports meet, the homeroom teacher decided to hold a celebration party and allocated funds to purchase prizes for the athletes. The goal is to maximize the value of the prizes bought within the allocated budget, which will help replenish their energy and stamina.

Input Format

The first line contains two integers, n (n ≤ 500) and m (m ≤ 6000), where n represents the number of prize types to be purchased, and m represents the allocated budget.
The next n lines each contain three integers: v, w, and s, representing the price, value (note: price and value are different concepts), and the maximum purchasable quantity (anywhere from 0 to s items) of the I-th prize, respectively. Here, v ≤ 100, w ≤ 1000, and s ≤ 10.

Output Format

A single line containing an integer, which represents the maximum value achievable from this purchase (note: this refers to value, not price).

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

1040