#include <stdio.h>
using namespace std;
int d[5001],v[5001],P[5001][10001],V[5001][10001],D[5001][10001];
int n,C,i,j;
int max(int a,int b)
{
	if(a>b) return a;
	else return b;
}
void ComputeV(int n,int C)
{
	for(i=0;i<=n;i++) V[i][0]=0;
	for(j=1;j<=C;j++) V[0][j]=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=C;j++){
			if(j<d[i]) V[i][j]=V[i-1][j];
				else V[i][j]=max(V[i-1][j],V[i-1][j-d[i]]+v[i]);
		}
		
	}
	
}
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[n][C]);
	
		
	
		 	
		
		
		
	return 0;
}