记录编号	210554	评测结果	AAAAAAAAAA
题目名称	71.[NOIP 2006]开心的金明	最终得分	100
用户昵称	hejj	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-11-28 14:37:46	内存使用	0.31 MiB

#include<iostream> 
#include<cstdio>
using namespace std; 
int main() 
{ 
	int m,n,i,v; 
	int w[25],c[25],f[30001]; 
	freopen("happy.in","r",stdin);
	freopen("happy.out","w",stdout);
	cin>>m>>n; 
	for(i=1;i<=n;i++) 
	{ 
	cin>>w[i]>>c[i]; 
	c[i]*=w[i]; 
	} 
	for(i=1;i<=n;i++) 
	for(v=m;v>=w[i];v--) 
	if(f[v]<f[v-w[i]]+c[i]) 
	f[v]=f[v-w[i]]+c[i]; 
	cout<<f[m]; 
	return 0; 
}