#include <fstream>
using namespace std;
ifstream cin( "rucsac.in" );
ofstream cout( "rucsac.out" );

int n, g, v[ 10001 ], w[ 5001 ];
int sol, p[ 5001 ];

int main()
{
	int i, j;
	cin >> n >> g;
	for ( i = 1; i <= n; i++ )
		cin >> w[ i ] >> p[ i ];
	v[ 0 ] = 0;
	for ( i = 1; i <= n; i++ )
		for ( j = g - w[ i ]; j >= 0; j-- )
			if ( v[ j + w[ i ] ] < v[ j ] + p[ i ] )
			{
				v[ j + w[ i ] ] = v[ j ] + p[ i ];
				if ( v[ j + w[ i ] ] > sol )
					sol = v[ j + w[ i ] ];
			}
	cout << sol;
}