#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n,w;
    cin >> n >> w;
    vector<int> vals(n+1), weights(n+1);
    vector<vector<int>> dp(n+1, vector<int>(w+1, 0)); 
    for(int i = 1; i<=n; i++){
        cin >> weights[i] >> vals[i];
    } 
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=w; j++){
            if(weights[i] <= j) dp[i][j] = max(dp[i-1][j], vals[i] + dp[i-1][j-weights[i]]);
            else dp[i][j] = dp[i-1][j];
        }
    }
    // for(int i = 0; i<=n; i++){
    //     for(int j = 0; j<=w; j++){
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    cout << dp[n][w];

    return 0;
}