> #include<iostream>
> #include<algorithm>
> 
> using namespace std;
> 
> const int MAXN = 40012;
> 
> int n,cnt;
> bool dp[MAXN];
> int h[MAXN],a[MAXN],c[MAXN],r[MAXN];
> 
> void ZeroOne_Pack(int w,int v)
> {
>     for(int i=v;i>=w;i--) if(dp[i-w]) dp[i]=true,cnt=max(cnt,i);
> }
> void Complete_Pack(int w,int v)
> {
>     for(int i=w;v>=i;i++) if(dp[i-w]) dp[i]=true,cnt=max(cnt,i);
> }
> void Multiple_Pack(int w,int n,int v)
> {
>     if(w*n>=v) Complete_Pack(w,v);
>     else
>     {
>         for(int i=1;i<n;i*=2)
>         {
>             n-=i;
>             ZeroOne_Pack(i*w,v);
>         }
>         ZeroOne_Pack(n*w,v);
>     }
> }
> bool cmp(int i,int j)
> {
>     return a[i]<a[j];
> }
> int main()
> {
>     while(scanf("%d",&n)!=EOF)
>     {
>         cnt=0;
>         int h_=0,a_=0,c_=0;
>         memset(dp,false,sizeof(dp)); dp[0]=true;
>         for(int i=0;n-i>0;i++)
>         {
>             scanf("%d %d %d",&h[i],&a[i],&c[i]);
>             r[i]=i;
>         }
>         sort(r,r+n,cmp);
>         for(int i=0;n-i>0;i++) Multiple_Pack(h[r[i]],c[r[i]],a[r[i]]);
>         printf("%d\n",cnt);
>     }
>     return 0;
> }