记录编号	94494	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]采药	最终得分	100
用户昵称	Will	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2014-04-01 14:39:03	内存使用	0.29 MiB

#include <stdio.h>
int main() {
	int T,M;
	int value[110][1010];
	int c,v;
	int i,j;
	freopen("medic.in","r",stdin);
	freopen("medic.out","w",stdout);
	for(i=0;i<T+1;i++) value[0][i]=0;
	for(i=0;i<M+1;i++) value[i][0]=0;
	scanf("%d%d",&T,&M);
	for(i=1;i<M+1;i++){
		scanf("%d%d",&c,&v);
		for(j=1;j<T+1;j++) {
			if(c<=j) {
				if(value[i-1][j]>value[i-1][j-c]+v) 	
					value[i][j]=value[i-1][j];
				else
					value[i][j]=value[i-1][j-c]+v;
			}
			else
				value[i][j]=value[i-1][j];
		}		
	}
	printf("%d\n",value[M][T]);
	return 0;
}