#include <fstream>

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

const int NMAX = 5000;
const int GMAX =  10000;

int n,wt[NMAX],pr[NMAX],d[GMAX],G;

int main(){
    
    f >> n >> G;
    
    for(int i = 1;i <= n;++i)
        f >> wt[i] >> pr[i];
    
    d[0] = 1;
    for(int i = 1;i <= n;++i){
        for(int j = G;j >= 0;--j)
            if(j - wt[i] >= 0 && d[j - wt[i]] != 0)
                d[j] = std::max(d[j],d[j - wt[i]] + pr[i]);
    }
    
    g << d[G] - 1;
    
    return 0;
}