View Code of Problem 4056

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct S
{
    int w, c;
} s[100];

int main(void)
{
    int w, n;
    cin >> w >> n;
    int dp[w + 1] = {0};
    for (int i = 0; i < n; i++)
        cin >> s[i].w >> s[i].c;
    for (int i = 0; i < n;i++){
        for (int j = w; j >= s[i].w;j--){
            dp[j] = max(dp[j], dp[j - s[i].w] + s[i].c);
        }
    }
    cout << dp[w] << endl;
}