记录编号	230681	评测结果	AAAAAAAAAAAA
题目名称	[USACO]总分	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.303 s
提交时间	2016-02-22 22:22:33	内存使用	0.40 MiB

#include<cstdio>
#define max(a,b) a>b?a:b
int f[10005],p[10005],t[10005];
int read(){
	int x;char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-48;
	while(ch=getchar(),ch<='9'&&ch>='0')x=x*10+ch-48;
	return x;
}
int main(){
	freopen("inflate.in","r",stdin);
	freopen("inflate.out","w",stdout);
	int m,n;m=read();n=read();
	for(int i=1;i<=n;++i){
		p[i]=read();t[i]=read();
	}
	for(int i=1;i<=n;++i)
		for(int j=t[i];j<=m;++j){
			f[j]=max(f[j],f[j-t[i]]+p[i]);
		}
	
	printf("%d\n",f[m]);
	fclose(stdin);fclose(stdout);
	return 0;
}