#pragma GCC push_options
#pragma GCC optimize ("O3")

#include<iostream>
#include<vector>
#include<fstream>
#include<algorithm>

using namespace std;
#define cin f



ifstream f("rucsac.in");
int main(){
    int N, G;
    cin>>N>>G; 
    
    vector<int> valori(N),greutati(N),dp(G+1);
    for(int i=0;i<N;i++){
        cin>>greutati[i]>>valori[i];
    }
    for(int j=0;j<=G;j++){
        if(greutati[0]<=j){
            dp[j] = valori[0];
        }
    }

    for(int i=1;i<N;i++){
        for(int j= G;j>=greutati[i];j--){
            
            dp[j] = max(dp[j],dp[j-greutati[i]]+valori[i]);
            
            
        }
    }

    ofstream out("rucsac.out");
    out<<dp[G];
}