记录编号	318831	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.153 s
提交时间	2016-10-09 21:26:36	内存使用	0.52 MiB

/*
  Name: 宝物筛选COGS 
  Copyright: 
  Author: Go灬Fire 
  Date: 09/10/16 21:25
  Description: 宝物筛选，多重背包，二进制优化 
*/
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#define Begin freopen("treasure.in","r",stdin);freopen("treasure.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
using namespace std;
const int maxn=5010;
int n,tot,v[maxn],w[maxn],f[45000];
void Init();

int main(){
    Begin;
    Init();
    //system("pause");
    return 0;
}
void Init(){
	scanf("%d%d",&n,&tot);
	int cnt=0;
	for(int i=1;i<=n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		int t=1;
		while(z>=t){
			v[++cnt]=t*x;
			w[cnt]=t*y;
			z-=t;
			t<<=1;
		}
		if(z){
			v[++cnt]=z*x;
			w[cnt]=z*y;
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=tot;j>=w[i];j--){
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	printf("%d\n",f[tot]);
}