其实改对了模板还是挺开心的，不过发现AC率那么高就不开心了==，这题放在bestcoder上就是第二题的好么。

注意一下需要排序，我是把中间都打出来发现的这个问题==

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[40004];
int n,M,t;
struct node
{
    int cost,weight,num,height;
}num[300];
bool cmp(node a,node b)
{
    return a.height<b.height;
}
void zeropack(int cost,int weight,int height)
{
    for(int i=height;i>=cost;i--)
        dp[i]=max(dp[i-cost]+weight,dp[i]);
}
void completepack(int cost,int weight,int height)
{
    for(int i=cost;i<=height;i++)
        dp[i]=max(dp[i-cost]+weight,dp[i]);
}
void multipack(int cost,int weight,int num,int height)
{
    if(num*cost>=height)
    {
        completepack(cost,weight,height);
        return;
    }
    int k=1;
    while(k<num)
    {
        zeropack(k*cost,k*weight,height);
        num-=k;
        k*=2;
    }
    zeropack(cost*num,weight*num,height);
}
int main()
{
  //  freopen("cin.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        int maxn=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&num[i].cost,&num[i].height,&num[i].num);
            num[i].weight=num[i].cost;
            if(maxn<num[i].height) maxn=num[i].height;
        }
        sort(num+1,num+1+n,cmp);
     //   printf("hei=%d   ",maxn);
        memset(dp,0,sizeof(dp));
         for(int i=1;i<=n;i++) multipack(num[i].cost,num[i].weight,num[i].num,num[i].height);
         int tmp=0;
         for(int i=1;i<=maxn;i++)
         {
             if(tmp<dp[i]) tmp=dp[i];
            //printf("%d  ",dp[i]);
         }
        printf("%d\n",tmp);
    }
    return 0;
}