knapsack

#include <iostream>
#include <cstring>

using namespace std;

#define MAXN 1023

int valor[MAXN];
int aguenta[MAXN];
int peso[MAXN];
int dp[MAXN][MAXN];

int n;

int knapsack(int obj, int aguenta) {

    if (obj >= n || aguenta == 0)
        return 0;

    if (dp[obj][aguenta] >= 0)
        return dp[obj][aguenta];

    int nao_coloca = knapsack(obj+1, aguenta);
    int coloca     = -1;

    if (peso[obj] <= aguenta)
        coloca = valor[obj] + knapsack(obj+1, aguenta - peso[obj]);

    return dp[obj][aguenta] = max(nao_coloca, coloca);

}

int main() {

    int sum;
    cin >> sum >> n;

    for (int i = 0; i < n; i++)
        cin >> peso[i] >> valor[i];

    memset(dp, -1, sizeof(dp));
    cout << knapsack(0, sum) << endl;

    return 0;
}