#include <stdio.h>
#include <stdlib.h>
#define MAX 5000
#define MAXI 10000
int mat[2][MAXI+1], val[MAX+1], g[MAX+1];
int main() {
    FILE *fin, *fout;
    int n,max,i,j,x,maxim;
    fin=fopen("rucsac.in","r");
    fout=fopen("rucsac.out","w");
    fscanf(fin, "%d%d", &n, &max);
    for (i=1; i<=n; i++) {
        fscanf(fin, "%d%d", &g[i], &val[i]);
    }
    for (i=1; i<=n; i++) {
        for (j=1; j<=max; j++) {
            if (i%2==0) {
                x=0;
            } else {
                x=1;
            }
            maxim=mat[x][j];
            if(mat[x][j-g[i]]+val[i]>maxim && j-g[i]>=0) {
                maxim=val[i]+mat[x][j-g[i]];
            }
            mat[1-x][j]=maxim;
        }
    }
    fprintf(fout, "%d\n", mat[1-x][max]);
    fclose(fin);
    fclose(fout);
    return 0;
}