#include <fstream>
#define nmax 5010
#define gmax 10010

using namespace std;

int dp[3][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 = 0;

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

}

void scrie(){

    g<<dp[r][G];

}

int main(){

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

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

    return 0;

}