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

using namespace std;

int dp[2][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(){

    int r;

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

}

void scrie(){
/*
    if ( n % 2==0) g<<dp[1][G];
    else g<<dp[0][G];
*/
    g<<dp[1][G];
}

int main(){

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

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

    return 0;

}