#include <cstdio>

#define FILEIN "rucsac.in"
#define FILEOUT "rucsac.out"
#define NMAX 5001
#define SMAX 10005

int W[NMAX], P[NMAX];
int D[SMAX];

int N, G;

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &N, &G);

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

    D[0] = 0;
    int sol = 0;

    for ( int i = 1; i <= N; i++ ) {
        for ( int j = G - W[i]; j >= 0; j-- ) {
            if (D[j+W[i]] < D[j] + P[i]) {
                D[j+W[i]] = D[j] + P[i];
            }
        }
    }

    printf("%d\n", D[G]);

    return 0;
}