记录编号	373976	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]开心的金明	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-02-22 08:59:34	内存使用	0.43 MiB

#include<iostream>
#include<cstdio>
using namespace std;
#define is_num(tmp) (tmp<='9'&tmp>='0')
inline int in()
{
	char tmp(getchar());
	int res(0);
	while(!is_num(tmp))tmp=getchar();
	while(is_num(tmp))
		res=(res<<1)+(res<<3)+(tmp^48),
		tmp=getchar();
	return res; 
}
//#define LOCAL
int dp[30001];
int W,N;
int w,v;
int main()
{
#ifndef LOCAL
	freopen("happy.in","r",stdin);
	freopen("happy.out","w",stdout);
#endif
	W=in(),N=in();
	for(int i=1;i<=N;++i)
	{
		v=in(),w=in();
		w*=v;
		for(int j=W;j>=v;--j)
			dp[j]=max(dp[j-v]+w,dp[j]); 
	}
	cout<<dp[W];
}