#include <fstream>

std::ifstream f("rucsac.in");
std::ofstream g("rucsac.out");

const int NMAX = 10005;
int n,G,greutate,profit,dp[2][NMAX];

int main(){
    
    f >> n >> G;
    
    for(int i = 1;i <= n;++i){
        
        f >> greutate >> profit;
        
        int t = i % 2;
        for(int j = 0;j <= G;++j){
            
            if(j < greutate)
                dp[t][j] = dp[1 - t][j];
            else
                dp[t][j] = std::max(dp[1 - t][j],dp[1 - t][j - greutate] + profit);
        }
    }
    
    g << dp[n % 2][G];
    
    return 0;
}