#include <fstream>
#define nmax 5000
#define gmax 10000

using namespace std;

int dp[nmax][gmax], w[nmax], p[nmax];
int n, G;

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

void citeste(){

    f>>n>>G;
    for(int i=1; i<=n; ++i){
        f>>w[i]>>p[i];
    }

}

int maxim(int x, int y){

    if ( x > y ) return x;
    return y;

}

void rezolva(){

    for(int i=0; i<nmax; ++i)
        for(int j=0; j<gmax; ++j) dp[i][j] = 0;

    for(int i=1; i<=n; ++i){
        for(int j=0; j<=G; ++j){
            dp[i][j] = dp[i-1][j];
            if (w[i] <= j)
                dp[i][j] = maxim(dp[i][j], dp[i-1][ j-w[i] ] + p[i]);
        }
    }

}

void scrie(){
/*
    for(int i=1; i<=n; ++i){
        for(int j=0; j<=G; ++j) g<<dp[i][j]<<" ";
        g<<"\n";
    }
*/
    g<<dp[n][G];
}

int main(){

    citeste();
    rezolva();
    scrie();

    f.close();
    g.close();

    return 0;

}