#include <fstream>

using namespace std;

ifstream fin ( "rucsac.in" ) ;
ofstream fout ( "rucsac.out" ) ;

int n , G , sol , i , j ;
int g[5005] , p[5005] , vect[100005] ;

int main()
{
    fin >> n >> G ;

    for ( i = 1 ; i <= n ; i ++ ) {
        fin >> g[i] >> p[i] ;
    }

    vect [0] = 0 ;

    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = G - g[i] ; j >= 0 ; j -- ) {
            if ( vect[j+g[i]] < vect[j] + p[i] ) {
                vect[j+g[i]] = vect[j] + p[i] ;
                if ( sol < vect[j] + p[i] ) {
                    sol = vect[j] + p[i] ;
                }
            }
        }
    }

    fout << sol ;
    return 0;
}