#include <iostream>
#include <cstdio>
#include <cassert>

#define Nmax 5001

using namespace std;

int N, G, cont;
int W[Nmax], P[Nmax];
int castig[2][Nmax << 1];

void citire(){

    assert( freopen("rucsac.in", "r", stdin) );

    assert( scanf("%d%d", &N, &G) == 2 );

    for(int i = 1; i <= N; ++i)
        assert ( scanf("%d%d", &W[i], &P[i]) == 2 ) ;
}

void dinamica(){

    for(int i = 1, cont = 0; i <= N; i++, cont = 1 - cont)
        for(int j = 0; j <= G; ++j){

            castig[1 - cont][j] = castig[cont][j];

            if(W[i] <= j)
                castig[1 - cont][j] = max( castig[1 - cont][j], castig[cont][j - W[i]] + P[i] );
        }
}

void afis(){

    assert ( freopen("rucsac.out", "w", stdout) );

    assert ( printf("%d\n", castig[cont][G]) );
}


int main(){

    citire();
    dinamica();
    afis();

    return 0;
}