记录编号	465599	评测结果	AAAAAAAAAA
题目名称	71.[NOIP 2006]开心的金明	最终得分	100
用户昵称	Hyoi_cerron	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2017-10-27 15:00:58	内存使用	0.43 MiB

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,w[35],v[35],dsc[30010];
int main()
{
	freopen("happy.in","r",stdin);
    freopen("happy.out","w",stdout);
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
        w[i]*=v[i];//重要度*价格
    }
       
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)//价格不超过总钱数 
        {
            dsc[j]=max(dsc[j],dsc[j-v[i]]+w[i]);//dp 
        }
    }
    cout<<dsc[m]<<endl;
    return 0;
}