1
//https://www.xinyoudui.com/ac/contest/747005D6B0006AA046984F6/problem/7245
2
#include<bits/stdc++.h>
3
using namespace std;
4
const int N=1e5+10;
5
const int MAXW=4*1e4+10;
6
int n,W;
7
long long v[N],w[N],m[N];
8
int top=0;
9
long long dp[MAXW];
10
int main()
11
{
12
    cin>>n>>W;
13
    for(int i=1;i<=n;i++)
14
    {
15
        cin>>v[i]>>w[i]>>m[i];
16
    }
17
    top=n;
18
    for(int i=1;i<=n;i++)
19
    {
20
        long long ans=2;
21
        long long ans2=m[i]-1;
22
        for(int j=1;j<=log(m[i]+1);j++)
23
        {
24
            top++;
25
            v[top]=v[i];
26
            w[top]=w[i];
27
            m[top]=min(ans,ans2);
28
            ans2-=ans;
29
            ans*=2;
30
            v[top]*=m[top];
31
            w[top]*=m[top];
32
        }
33
        m[i]=1;
34
    }
35
    // for(int i=1;i<=top;i++)
36
    // {
37
    //     cout<<v[i]<<' '<<w[i]<<' '<<m[i]<<endl;
38
    // }
39
    for(int i=1;i<=top;i++)
40
    {
41
        for(int j=W;j>=w[i];j--)
42
        {
43
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
44
        }
45
    }
46
    cout<<dp[W];
47
    return 0;
48
}