#include <fstream>
#define NMAX 5008
#define GMAX 10008
using namespace std;

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

int n, G;
struct obiect{
    int w, p;
}v[NMAX];

int d[2][GMAX];
int ant, crt;

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>>v[i].w>>v[i].p;
}

void pd(){
    ant = 1; crt = 0;

    int i, g;
    for(i = 1; i<= n; ++i){
        for(g = 0; g <= G; ++g){
            d[crt][g] = d[ant][g];
            if( d[crt][g] <= d[ant][g - v[i].w] + v[i].p && v[i].w <= g)
                d[crt][g] = d[ant][g - v[i].w] + v[i].p;
        }
        ant = 1-ant; crt = 1 - crt;
    }
}