#include <cstdio>

#define inFile  "rucsac.in"
#define outFile "rucsac.out"

#define NMAX    5001
#define GMAX    10001

#define max(a,b)    (a>b ? a:b)

int Sol[2][GMAX],
    N, G, W, P, l, pos;

int main()
{
    freopen( inFile, "r", stdin );
    scanf("%d %d", &N, &G);

    for( int i = 1; i <= N; i++, l = 1 - l )
    {
        scanf("%d %d", &W, &P);
        for( pos = 0; pos <= G; pos++ )
        {
            Sol[1-l][pos] = Sol[l][pos];
            if( W <= pos )
                Sol[1-l][pos] = max( Sol[1-l][pos], Sol[l][pos - W] + P );
        }
    }

    printf("%d\n", Sol[l][G]);
    return 0;
}