#include <bits/stdc++.h>

using namespace std;

int main() {
    int n,w;
    while(cin>>n>>w){
        vector<vector<int>> dp(n+1,vector<int>(w+1));
        for(int i=1;i<=n;i++){
            int x,y;cin>>x>>y;
            for(int j=0;j<=w;j++){
                if(j>=x)dp[i][j]=max(dp[i-1][j],dp[i][j-x]+y);
                else dp[i][j]=dp[i-1][j];
            }
        }
        cout<<dp[n][w]<<endl;
    }
}

完全背包问题的差异就是，我放了一个物品之后，还可以再放，直到不能放为止，也就是当前物品不需要进行物品的id的收缩，只需要背包的收缩，每个都求自己的收缩，如果不能收缩了，说明需要不放入了，就去收缩到前面的最佳状态