C :

#include "stdio.h"
int n,m;
int a[10000],b[10000],c[10000],f[10001];
int main()
{
	int i,j;
	int k,s;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for(i=0;i<n;i++)
	{
		if(c[i]==0||c[i]*a[i]>=m)
		{
			for(j=a[i];j<=m;j++)
				if(f[j-a[i]]+b[i]>f[j])
					f[j]=f[j-a[i]]+b[i];
		}
		else
		{
			k=1,s=c[i];
			while(k<s)
			{
				
				for(j=m;j>=k*a[i];j--)
					if(f[j]<f[j-k*a[i]]+k*b[i])
						f[j]=f[j-k*a[i]]+k*b[i];
					s-=k;
					k*=2;
			}
			for(j=m;j>=s*a[i];j--)
				if(f[j]<f[j-s*a[i]]+s*b[i])	
					f[j]=f[j-s*a[i]]+s*b[i];
		}
	}
	printf("%d\n",f[m]);
	return 0;
}

C++ :

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int m,n,f[10001]={0},w[10001],v[10001],p[10001];
int a[10001],b[10001],l,r;
void init();
void work();
void insert(int,int);
int main()
{
	init();
	work();
	return 0;
}
void init()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>p[i];
}
void work()
{
	for(int i=1;i<=n;i++)
	{
		if(p[i]==0||p[i]>m/v[i])p[i]=m/v[i];
		for(int d=0;d<v[i];d++)
		{
			l=1;
			r=0;
			for(int j=0;j<=(m-d)/v[i];j++)
			{
				insert(j,f[j*v[i]+d]-j*w[i]);
				if(a[l]<j-p[i]) l++;
				f[j*v[i]+d]=b[l]+j*w[i];
			}
		}
	}
	cout<<f[m]<<endl;
}
void insert(int x,int y)
{
	while(l<=r && b[r]<=y) r--;
	r++;a[r]=x;b[r]=y;
}