package Acwing算法练习.第五章dp;

import java.util.Scanner;
//多重背包问题可以最多有s[i]件，完全背包问题的物品有无数个
//有二进制进行优化
//每次分组为1,2,4,8,16...直到s,每次在一组里用01背包问题（选与不选）找到最优，01背包问题问题用一维优化，最后全局最优。
public class 多重背包问题优化 {
    static int N =  2500,M = 2010;
    static int n,m;
    static int[] v = new int[N],w = new int[N];
    static int f[] = new int[M];//体积
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int cnt = 0;//分组的组别
        for(int i=1;i<=n;i++)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int s = sc.nextInt();
            int k = 1;//组别里的个数
            while(k<=s)
            {
                cnt++;//先加一次
                v[cnt] = a*k;//整体体积
                w[cnt] = b*k;// 整体价值
                s-=k;// s要减小
                k*=2;// 组别里的个数增加
            }
            if(s>0)
            {
                cnt++;
                v[cnt] = a*s;
                w[cnt] = b*s;
            }
        }

        n = cnt;
        //01背包问题优化
        for(int i=1;i<=n;i++)
        {
            for(int j=m;j>=v[i];j--)
            {
                f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
            }
        }
        System.out.println(f[m]);
    }

}