#include <stdio.h>

#define MAXN 5001
#define MAXG 10001

int W[MAXN], P[MAXN];
int Optim[MAXG];

int main() {
    FILE *fin = fopen("rucsac.in", "r");
    FILE *fout = fopen("rucsac.out", "w");

    int N, G;
    fscanf(fin, "%d %d", &N, &G);

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

    for (int i = 0; i <= G; ++i)
        Optim[i] = 0;

    int sol = 0;

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

    fprintf(fout, "%d\n", sol);

    fclose(fin);
    fclose(fout);
    return 0;
}