Celebration party （ A one-dimensional ）

In order to celebrate the class's first place in the school sports meeting , The head teacher decided to hold a celebration meeting , For this purpose, allocate funds to buy prizes to reward athletes .

It is expected that the allocation amount can buy the most valuable prize , It can replenish their energy and physical strength .

Input format

Two numbers in the first line n,m, among n Represents the number of prizes you want to buy ,m Indicates the appropriation amount .

Next n That's ok , Each row 3 Number ,v、w、s, Separate indication control I The price of each prize 、 value （ Price and value are different concepts ） And the maximum quantity you can buy （ buy 0 Pieces arrive at s Pieces can be ）.

Output format

a line ： a number , Indicates the maximum value that can be obtained from this purchase （ Be careful ！ It's not the price ）.

Data range

n≤500,m≤6000n≤500,m≤6000,
v≤100,w≤1000,s≤10v≤100,w≤1000,s≤10

sample input ：

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

sample output ：

1040

#include <bits/stdc++.h>

using namespace std;

const int M = 6010;

int n, m;
int f[M];

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i ++)// The first dimension traverses the types of items from small to large ( Number of prizes )
    {
        int v, w, s;// Volume ( Price )、 value ( take max)、 Number 
        scanf("%d%d%d", &v, &w, &s);
        for(int j = m; j >= v; j --)// The second dimension traverses the backpack capacity from large to small ( Appropriation amount )
            for(int k = 0; k <= s && k * v <= j; k++)// The third dimension traverses the number from small to large 
                f[j] = max(f[j], f[j - k * v] + k * w);
    }

    printf("%d", f[m]);
    
    return 0;
}