DP

#include<iostream>
using namespace std;

const int MAX_N = 1050;
int n, m;
int w[MAX_N], v[MAX_N];
int dp[MAX_N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i] >> v[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= 0; j--){
            if(j >= w[i]){
                dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
            }
        }
    }
    cout << dp[m];
    return 0;
}