题解 | #[NOIP2006]开心的金明#

#include<iostream>
using namespace std;
const int M=30010;
int p[M],w[M],n,N,f[M];
int main(){
    cin>>N>>n;
    for(int i=1;i<n+1;i++)cin>>w[i]>>p[i];
    
    for(int i=1;i<n+1;i++){
        for(int j=N;j>=w[i];j--){
            f[j]=max(f[j],f[j-w[i]]+w[i]*p[i]);
        }
    }
    
    cout<<f[N];
    
    
    return 0;
}