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

int W[NMAX], P[NMAX];
int sol[GMAX];

int main() {
    FILE *fin = fopen("rucsac.in", "r");
    if(fin == NULL)
        return -1;
    int N, G; 
    
    fscanf(fin, "%d%d", &N, &G);
    for(int i = 0; i < N; i ++) {
        fscanf(fin, "%d%d", &W[i], &P[i]);
    }

    for(int i = 0; i < N; i ++)
        for(int j = G; j >= W[i]; j --)
            if(sol[j] < sol[j-W[i]] + P[i])
                sol[j] = sol[j-W[i]] + P[i];
    
    FILE *fout = fopen("rucsac.out", "w");
    if (fout == NULL)
        return -1;
    fprintf(fout,"%d",sol[G]);

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