#include<stdio.h>
using namespace std;
FILE *f1=fopen("rucsac.in","r");
FILE *f2=fopen("rucsac.out","w");
int greutate[5001],n,g,cost[5001],maxs,sol[10001],i,j;
int main(){
    fscanf(f1,"%d%d",&n,&g);
    for (i=1;i<=n;i++){
        fscanf(f1,"%d%d",&greutate[i],&cost[i]);
    }
    fclose(f1);
    sol[0]=0;
    for (i=1;i<=n;i++)
        for (j=g-greutate[i];j>=0;j--)
         if (sol[j+greutate[i]]<sol[j]+cost[i]){
                sol[j+greutate[i]]=sol[j]+cost[i];
                if (maxs<sol[j+greutate[i]]) maxs=sol[j+greutate[i]];
         }
    fprintf(f2,"%d",maxs);
    fclose(f2);
    return 0;
}