//TEF
 # include <fstream>
 # include <cstring>
 # include <algorithm>
 
 # define dim 10005
 # define dim2 5005
 
 using namespace std;
 
 ifstream f("rucsac.in");
 ofstream g("rucsac.out");
 
 int N, G;
 int w[ dim2 ], p[ dim2 ];
 int a[ 5 ][ dim ];
 
 void citire()
 {
	 int i;
	 f >> N >> G;
	 for ( i = 1 ; i <= N ; i++ )
		 f >> w[ i ] >> p[ i ];
 }
 
 void rezolva()
 {
	 int i, j;
	 int sub = 1;
	 
	 for ( i = 1 ; i <= N ; i++ )
	 {
		 for ( j = 0 ; j <= G ; j++ )
		 {
			 if ( sub == 2 )
			 {
				 a[ sub ][ j ] = a[ sub - 1 ][ j ];
				 if ( w[ i ] <= j )
					 a[ sub ][ j ] = max( a[ sub ][ j ], a[ sub - 1 ][ j - w[ i ] ] + p[ i ] );
			 }
			 else
				 if ( sub == 1 )
				 {
					 a[ sub ][ j ] = a[ sub + 1 ][ j ];
					 if ( w[ i ] <= j )
						 a[ sub ][ j ] = max( a[ sub ][ j ], a[ sub + 1 ][ j - w[ i ] ] + p[ i ] );
				 }
		 }
		 
		 if ( sub == 1 )
			 sub++;
		 else
			 sub--;
	 }
	 
	 if ( sub == 1 )
		 sub++;
	 else
		 sub--;
	 
	 g << a[ sub ][ G ] << "\n";
 }
  
 int main()
 {
	 citire();
	 rezolva();
	 return 0;
 }