#include <cstdio>
#define NMAX 5005
#define GMAX 10005
using namespace std;

int v[NMAX], g[NMAX], n, G, d[GMAX];

int main() {

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

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

    for(int i=1; i<=G; i++) {
        if(g[1] > i)
            continue;
        d[i] = v[1];
    }

    for(int i=2; i<=n; i++) {
        for(int j=G; j>=g[i]; j--) {
            if(d[j - g[i]] + v[i] > d[j]) {
                d[j] = d[j - g[i]] + v[i];
            }
        }
    }

    fprintf(fout, "%d", d[G]);

    return 0;
}