Untitled

#include 
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int n, W;
int weights[105], values[105];
ll dp[105][100005];
ll rec(int i, int value_left) {
    if(value_left == 0) {
        return 0;
    }
    if(i == n) {
        return 1e18;
    }
    if(dp[i][value_left] != -1) {
        return dp[i][value_left];
    }
    ll result = 1e18; // 1 i 18 nuli posle edinicata 1000...0
    result = min(result, rec(i + 1, value_left));
    if(value_left - values[i] >= 0) {
        result = min(result, rec(i + 1, value_left - values[i]) + weights[i]);
    }
    dp[i][value_left] = result;
    return result;
}
int main()
{
    cin >> n >> W;
    int sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> weights[i] >> values[i];
        sum += values[i];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= sum; j++) {
            dp[i][j] = -1;
        }
    }
    for(int i = sum; i >= 0; i--) {
        if(rec(0, i) <= W) {
            cout << i << endl;
            break;
        }
    }
    
    return 0;
}