Knapsack 1

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1e9 + 7;
const int N = 1e5 + 5;

int n , w;
int dp[N];
int a[N];
int b[N];

signed main()
{
    cin >> n >> w;
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
    }
    dp[0] = 0;
    for(int j = 0; j < n; j++){
        for(int i = w; i >= 1; i--){
            if(i < a[j])
                continue;
            dp[i] = max(dp[i] , dp[i - a[j]] + b[j]);
        }
    }
    cout << dp[w] << endl;

}