#include<stdio.h>
long n,s,uz[2][10005];
FILE*f=fopen("rucsac.in","r"),*g=fopen("rucsac.out","w");

struct obiecte{
long g,p;
}v[5005];


void citire(){
    fscanf(f,"%ld %ld ",&n,&s);
	for(long i=1;i<=n;i++){
	   fscanf(f,"%ld %ld ",&v[i].g,&v[i].p);
	}
	fclose(f);
}

int max(long a,long b){
    if(a>b){return a;}
	return b;
}

void pd(){
	long l=0;
	for(long i=1;i<=n;i++ ,l=1-l){
	   for(long j=0;j<=s;j++){
	      uz[1-l][j]=uz[l][j];
		  if(v[i].g<=j){
			uz[1-l][j]=max(uz[1-l][j],uz[l][j-v[i].g]+v[i].p);
		  }
		 
	   }
	}
	fprintf(g,"%ld ",uz[l][s]);
	fclose(g);
}

int main(){
citire();
pd();
return 0;
}