#include<stdio.h>
#include<string.h>
#define dim 5005
#define dim2 10005
using namespace std;

int n, GMax, g[dim], c[dim], CMax[dim2], uz[dim2][dim], S, i, k, MAX;


void read()
{
	FILE *f = fopen("rucsac.in","r");
	
	fscanf(f,"%d %d",&n,&GMax);
	
	for(i = 1; i <= n; i++)
		fscanf(f,"%d %d",&g[i],&c[i]);
	
	fclose(f);
}

void solve()
{
	for(S = 1; S <= GMax; S++)
	{
		for(i = 1; i <= n; i++)
		{
			if( g[i] <= S && uz[ S - g[i] ][ i ] == 0 )
			{
				if( CMax[S] < CMax[S - g[i]] + c[i] )
				{
					CMax[S] = CMax[S - g[i]] + c[i];
					for(k = 1; k <= n; k++)
						uz[S][k] = uz[S-g[i]][k]; 
					uz[S][i] = 1;	
					
					if(CMax[S] > MAX)
						MAX = CMax[S];
				}			
			}	
		}
	}
}


void print()
{
	FILE *g = fopen("rucsac.out","w");
	
	//fprintf(g,"%d\n",CMax[GMax]);
	fprintf(g,"%d\n",MAX);
	
	//for(i = 1; i <= n; i++)
	//{
	//	if(uz[GMax][i] == 1)
	//		fprintf(g,"%d ",i);
	//}
	//fprintf(g,"\n");
	fclose(g);
}


int main()
{
	read();
	solve();
	print();

return 0;
}