#include<stdio.h>
#define NMAX 5001
#define GMAX 10001

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

int g[NMAX], c[NMAX];
int optim[2][GMAX];
int N, G;
FILE *in, *out;

void copi() {
    for(int i = 0; i < GMAX; ++i) {
        optim[0][i] = optim[1][i];
    }
}

int main() {
    in = fopen(inFile, "r");
    out = fopen(outFile, "w");

    fscanf(in, "%d%d", &N, &G);
    for(int i = 1; i <= N; ++i) {
        fscanf(in, "%d%d", &g[i], &c[i]);
    }

    for(int i = 1; i <= N; ++i) {
        for(int j = g[i]; j <= G; ++j) {
            if(optim[0][j - g[i]] + c[i] > optim[0][j]) {
                optim[1][j] = optim[0][j - g[i]] + c[i];
            }
            else {
                optim[1][j] = optim[0][j];
            }
        }
        copi();
    }

    fprintf(out, "%d", optim[0][G]);

    fclose(in);
    fclose(out);

    return 0;
}