#include <cstdio>
#define NMAX 5005
#define GMAX 10001
using namespace std;
FILE *fin, *fout;
int n, g, d[2][GMAX];
struct o { int g, p; }ob[NMAX];
int mx (int a, int b) { return ((a>b)?a:b); }
int main()
{
    int i, w;
    fin=fopen("rucsac.in", "r"); fout=fopen("rucsac.out", "w");
    fscanf (fin, "%d%d", &n, &g); for (i=1; i<=n; ++i) { fscanf (fin, "%d%d", &ob[i].g, &ob[i].p); }
    for (i=1; i<=n; ++i) for (w=0; w<=g; ++w) {
        d[i%2][w]=d[(i+1)%2][w];
        if (ob[i].g<=w) d[i%2][w]=mx(d[i%2][w], d[(i+1)%2][w-ob[i].g]+ob[i].p);
    }
    fprintf (fout, "%d\n", d[n%2][g]);
    fclose(fin); fclose(fout);
    return 0;
}