/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include <bits/stdc++.h>

const char IN [ ] =  "rucsac.in" ;
const char OUT [ ] = "rucsac.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

const int MAX_N = 5014 ;
const int GMAX = 10014 ;

int W [ MAX_N ] ;
int P [ MAX_N ] ;
int dp [ GMAX ] ;

int main()
{
    int n , g ;
    fin >> n >> g ;
    FORN ( i , 1 , n ) {
        fin >> W [ i ] >> P [ i ] ;
    }
    int s = 0 ;
    FORN ( i , 1 , n ) {
        FORNBACK ( j , s , 0 ) {
            if ( j + W [ i ] <= g and dp [ j + W [ i ] ] < dp [ j ] + P [ i ] ) {
                dp [ j + W [ i ] ] = dp [ j ] + P [ i ] ;
            }
        }
        s = s + W [ i ] ;
    }
    int solution = 0 ;
    FORN ( i , 0 , g ) {
        solution = max ( solution , dp [ i ] ) ;
    }
    fout << solution << '\n' ;
    return 0;
}