#include<fstream>
#include<cstdio>

using namespace std;

const int MaxN = 5001;
const int MaxG = 10001;

const char InFile[] = "rucsac.in";
const char OutFile[] = "rucsac.out";

int N,G,w[MaxN],p[MaxN],din[2][MaxG];

int max1(int a , int b )
{
	return a > b ? a : b;
}

int main()
{
	freopen( InFile , "r" , stdin );
	freopen( OutFile , "w" , stdout );
	int i,l,bw;
	scanf("%d%d" , &N , &G );
	for( i = 1 ; i <= N ; i++ )
		scanf("%d%d" , &w[i] , &p[i] );
	for( i = 1 , l = 0 ; i <= N ; ++i , l = 1-l )
		for( bw = 0 ; bw <= G ; ++bw )
			{
				din[1-l][bw] = din[l][bw];
				if( w[i] <= bw )
					din[1-l][bw] = max1( din[1-l][bw] , din[l][bw - w[i]] + p[i] );
			}
	printf("%d\n" , din[l][G]);
	return 0;
}