Untitled

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
int n, w;
int weight[101];
int value[101];
ll memo[101][100001];
ll knapsack(int at, int weight_left) {
    if(at == n or weight_left == 0) {
        return 0;
    }
    if(memo[at][weight_left] != -1) {
        return memo[at][weight_left];
    }
    ll result = 0;
        result = max(result, knapsack(at + 1, weight_left));
       
        if(weight_left - weight[at] >= 0) {
            result = max(result, knapsack(at + 1, weight_left - weight[at]) + value[at]);
        }
    return memo[at][weight_left] = result;
}
int main() {
    cin >> n >> w;
    for(int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= w; j++) {
            memo[i][j] = -1;
        }
    }
    cout << knapsack(0, w) << endl;
    return 0;
}
/*
 3 8
 
 3 30
 4 50
 5 60
 knapsack(0, 8) --> max(knapsack(1, 8), knapsack(1, 8 - 3) + 30)
 knapsack(1, 8) --> max(knapsack(2, 8), knapsack(2, 4) + 50)
 knapsack(2, 8) --> max(knapsack(3, 8), knapsack(3, 3) + 60)
 knapsack(3, 8) = 0
 knapsack(3, 3) = 0
 
 **/