记录编号	163933	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]开心的金明	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-05-27 10:30:55	内存使用	0.54 MiB

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <fstream>
#define cin fin
#define cout fout

using namespace std;

ifstream fin("happy.in");
ofstream fout("happy.out");
const int MAXN = 30001, MAXM = 26;
unsigned int v[MAXM], w[MAXN], dp[MAXN] = {0}, m, n;

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		cin >> v[i] >> w[i];
	}
	
	for(int i = 1; i <= m; i ++)
		for(int j = n; j >= v[i]; j --)
			dp[j] = max(dp[j - v[i]] + v[i] * w[i], dp[j]);
		
	cout << dp[n] << endl;
//	system("pause");
	return 0;
}