#include <stdio.h>
int g[5001],p[5000],max[2][10001];
inline int maxim(int a,int b){
    int sol;
    if(a>=b){
        sol=a;
    }else{
        sol=b;
    }
    return sol;
}
int main(){
    int n,G,i,gc,poznow,pozbef,aux;
    FILE *fin,*fout;
    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",&g[i],&p[i]);
    }
    poznow=0;
    pozbef=1;
    for(i=1;i<=n;i++){
        for(gc=1;gc<=G;gc++){
            max[poznow][gc]=max[pozbef][gc];
            if((gc>=g[i])&&(max[poznow][gc]<max[pozbef][gc-g[i]]+p[i])){
                max[poznow][gc]=max[pozbef][gc-g[i]]+p[i];
            }
        }
        aux=poznow;
        poznow=pozbef;
        pozbef=aux;
    }
    fprintf(fout,"%d\n",max[pozbef][G]);
    fclose(fin);
    fclose(fout);
    return 0;
}