# include <fstream>
 # include <cstring>
 # include <algorithm>
 # include <vector>
 
 
 using namespace std;
 
 ifstream f("rucsac.in");
 ofstream g("rucsac.out");
 
 int dp[ 5005 ][ 5005 ], W[ 5005 ], P[ 5005 ];
 int N, G;
 
 void citire()
 {
	 int i;
	 f >> N >> G;
	 for ( i = 1 ; i <= N ; i++ )
		 f >> W[ i ] >> P[ i ];
	 
 }
 
 void rezolva()
 {
	 int i, j;
	 for ( i = 1 ; i <= N ; i++ )
		 for ( j = 0 ; j <= G ; j++ )
		 {
			 dp[ i ] [ j ] = dp[ i - 1 ][ j ];
			 
			 if ( W[ i ] <= j )
				 dp[ i ][ j ] = max( dp[ i ][ j ], dp[ i - 1 ][ j - W[ i ] ] + P[ i ] );
		 }
		 
	g << dp[ N ][ G ];
 }
 
 int main()
 {
	 citire();
	 rezolva();
	 return 0;
 }