#include <fstream>

using namespace std ;

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

int N , G , W[5005] , P[5005] ;
int S1[10005] , S2[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 )
        {
         S2[j] = S1[j] ;
         if ( W[i] <= j )
            S2[j] = max ( S2[j] , S1[j-W[i]] + P[i] ) ;
        }
     for ( int j = 0 ; j <= G ; ++j )
        S1[j] = S2[j] ;
    }
 g << S1[G] ;
}