View Code of Problem 611

//背包问题
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>

const int inf = 0x3f3f3f;
const int MAXN = 1e2+10;
const int MMAXN = 1e3+10;
using namespace std;
int w[MAXN];
int num[MAXN];
int dp[MMAXN];

void init(){
    for(int i=1;i<MMAXN;i++)
        dp[i] = inf;
   // for(int i=1;i<20;i++)
        //cout<<dp[i]<<endl;
    //dp[0] = 0;
}

int main()
{
    int n,m;
   // cout<<inf<<endl;
    while(scanf("%d%d",&m,&n)!=EOF){
        init();
        for(int i=0;i<n;i++){
            scanf("%d%d",&w[i],&num[i]);
        }
        for(int i=0;i<n;i++){
            for(int j=num[i];j>0;j--){
                for(int k=m;k>=w[i];k--){
                    dp[k] = min(dp[k],dp[k-w[i]]+1);
                }
            }
        }
        if(dp[m]==inf)cout<<"Naivete"<<endl;
        else cout<<dp[m]<<endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}