#include <cstdio>
const int NMAX = 5000;
const int GMAX = 10000;
using namespace std;
int d[2][GMAX+5];
struct OBIECT {
    int w, p;
}v[NMAX+5];
int main()
{
    freopen ( "rucsac.in", "r", stdin );
    freopen ( "rucsac.out", "w", stdout );
    int n, g, w, p, i, l, cw;
    scanf ( "%d%d", &n, &g );
    for ( i = 1 ; i <= n ; ++ i ) {
        scanf ( "%d%d", &w, &p );
        v[i].w = w;
        v[i].p = p;
    }
    l = 0;
    for ( i = 1 ; i <= n ; ++ i ) {
        for ( cw = 0 ; cw <= g ; ++ cw ) {
            d[1-l][cw] = d[l][cw];
            if ( v[i].w <= cw )
                d[1-l][cw] = d[1-l][cw] > d[l][cw-v[i].w] + v[i].p ? d[l][cw] : d[l][cw-v[i].w] + v[i].p;
        }
        l = 1 - l;
    }
    printf ( "%d\n", d[l][g] );
    return 0;
}