#include <stdio.h>
using namespace std;
int d[10001],v[10001],V[3][10001],D[3][10001];
int n,C,i,j,vect[3]={0,1,2};
void inversare()
{
	int aux;
	aux=vect[1];
	vect[1]=vect[2];
	vect[2]=aux;
}
int max(int a,int b)
{
	if(a>b) return a;
	else return b;
}
void ComputeV(int n,int C)
{
	for(i=1;i<=n;i++){
		for(j=1;j<=C;j++){
			if(j<d[i]) V[vect[1]][j]=V[vect[2]][j];
				else V[vect[1]][j]=max(V[vect[2]][j],V[vect[2]][j-d[i]]+v[i]);
		}
		inversare();
		
	}
	
}
int main()
{
	FILE * fin=fopen("rucsac.in","r");
	FILE * fout=fopen("rucsac.out","w");
	fscanf(fin,"%d%d",&n,&C);
	for(i=1;i<=n;i++)
		fscanf(fin,"%d%d",&d[i],&v[i]);
		
	ComputeV(n,C);
	
			fprintf(fout,"%d ",V[vect[2]][C]);
	
		
	
		 	
		
		
		
	return 0;
}