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

int n, GMax, g[ dim ], c[ dim ], CMax[ dim2 ], i, j, 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( i = 1; i <= n; ++i )
	{
		for( j = GMax - g[ i ]; j >= 0; --j )
			if( CMax[ j + g[ i ] ] < CMax[ j ] + c[ i ] )
			{
				CMax[ j + g[ i ] ] = CMax[ j ] + c[ i ];
				if(CMax[ j + g[ i ] ] > MAX)
					MAX = CMax[ j + g[ i ] ];			
			}
	}
}

void print()
{
	FILE *g = fopen("rucsac.out","w");
	
	fprintf( g,"%d\n", MAX);
	
	fclose( g );
}

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

	return 0;
}