#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=g[i];gc<=G;gc++){
max[poznow][gc]=maxim(max[pozbef][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;
}