#include <iostream>
#include <vector>

using namespace std;


int main(){
    freopen("rucsac.in.txt","r",stdin);
    freopen("rucsac.out","w",stdout);

    int n,g;
    cin >> n >> g;

    vector<int> w(n+1),p(n+1);
    for(int i = 0;i < n; ++i){
        cin >> w[i] >> p[i];
    }

    vector<int>dp(g+1,0);

    for(int i = 0;i < n; ++i){
        for(int cw = g; cw >= w[i]; --cw)
            dp[cw] = max(dp[cw],dp[cw-w[i]]+p[i]);
    }

    cout << dp[g] << '\n';

    return 0;
}