#include <fstream>
#define NMAX 5000
#define GMAX 10000
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, G;

int W[NMAX], P[NMAX];
int d[2][GMAX];

void init();
void pd();

int main(){
    init();
    pd();
    fout<<d[1][G]<<'\n';

    return 0;
}

void init(){
    fin>>n>>G;

    int i;
    for(i = 1; i<= n; ++i)fin>>W[i]>>P[i];
}

void pd(){

    int ant, crt;
    ant = 1; crt = 0;

    int i, g;
    for(i = 1; i<= n; ++i){
        for(g = 1; g <= G; ++g){
            d[crt][g] = d[ant][g];
            if( d[crt][g] <= d[ant][g - W[i]] + P[i] && W[i] <= g)
                d[crt][g] = d[ant][g - W[i]] + P[i];
        }
        ant = 1-ant; crt = 1 - crt;
    }
}