SNAPSACK, Dinh

#include <bits/stdc++.h>
using namespace std;
struct d{
    int w;
    int v;
};
int main()
{
    int n,s;
    cin>>s>>n;
    int f[s+1][n+1]={0};
    d a[n+1];
    for (int i=0; i<=s; i++)
        for (int j=0; j<=n; j++)
        f[i][j]=0;
    for(int i=1; i<=n; i++)
        cin>>a[i].w>>a[i].v;
    for (int i=1; i<=s; i++){
    for (int j=1; j<=n; j++){
        if (i-a[j].w>=0) f[i][j]=max(f[i-a[j].w][j-1]+a[j].v,f[i][j-1]);
        else f[i][j]=f[i][j-1];
    }
    }
    cout<<f[s][n];
    return 0;
}