View Code of Problem 4056

#include <bits/stdc++.h>
using namespace std;
int w[101], c[101];
int W, K;
int maxi = 0;
void dfs(int index, int sumW, int sumC){
    if(index == K){
        return;
    }
    dfs(index+1, sumW, sumC);
    if(sumW+w[index]<=W){
        if(sumC+c[index]>maxi){
            maxi = sumC+c[index];
        }
        dfs(index+1, sumW+w[index], sumC+c[index]);
    }
}
int main(){ 
    while(cin>>W>>K){
        for(int i = 0; i<K; i++){
            cin>>w[i]>>c[i];
        }
        dfs(0, 0, 0);
        cout<<maxi<<endl;
    }
    return 0;
}