记录编号	96205	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	雪狼	是否通过	通过
代码语言	C++	运行时间	0.742 s
提交时间	2014-04-11 16:56:05	内存使用	0.46 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define REP(i,a,b) for(int i=a;i!=b+1;++i)
#define uREP(i,a,b) for(int i=a;i>=b;--i)
#define CLR(c,x) memset(c,x,sizeof(c))
#define maxn 40000+10
using namespace std;

int n,W;
int v,w,m;
int DP[maxn];

void Try(int v,int w){
	uREP(i,W,w)DP[i]=max(DP[i],DP[i-w]+v);
	REP(i,1,W)DP[i]=max(DP[i-1],DP[i]);
}

void tri(int v,int w,int m){
	int id=1;
	while(1){
		if(m>id)Try(v*id,w*id),m-=id;
		else {Try(v*m,w*m);return;}
		id<<=1;
	}
}

void setIO(string s){
	string in=s+".in",out=s+".out";
	freopen(in.c_str(),"r",stdin);
	freopen(out.c_str(),"w",stdout);
}

void work(){
	CLR(DP,0);
	scanf("%d%d",&n,&W);
	REP(op,1,n){
		scanf("%d%d%d",&v,&w,&m);
		tri(v,w,m);
	}
	printf("%d\n",DP[W]);
}
		

int main(){
	setIO("treasure");
	work();
	return 0;
}