#include <cstdio>
#include <algorithm>

#define MAXN 5000
#define MAXG 10000

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

int g[MAXN + 2], p[MAXN + 2];
int d[2][MAXG+2];

int main() {
    int n, gr, rez, l = 0;

    fscanf(fin, "%d%d", &n, &gr);

    for (int i = 1; i <= n; i++)
        fscanf(fin, "%d%d", &g[i], &p[i]);

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= gr; j++) {
            if (g[i] <= j)
                d[1-l][j] = std::max( d[l][j], d[l][j - g[i]] + p[i] );
            else
                d[1-l][j] = d[l][j];
        }
        l = 1 - l;
    }
    rez = d[l][gr];
    fprintf(fout, "%d", rez);
    return 0;
}