#include <fstream>

using namespace std ;

ifstream f("rucsac.in") ;
ofstream g("rucsac.out") ;

int N , G , W[5005] , P[5005] , S[5005][10005] ;

int main ()
{
 f >> N >> G ;
 for ( int i = 1 ; i <= N ; ++i )
    f >> W[i] >> P[i] ;
 for ( int i = 1 ; i <= N ; ++i )
    for ( int j = 0 ; j <= G ; ++j )
        {
         S[i][j] = S[i-1][j] ;
         if ( W[i] <= j )
            S[i][j] = max ( S[i][j] , S[i-1][j-W[i]] + P[i] ) ;
        }
 g << S[N][G] ;
}