#include <fstream>

using namespace std ;

const int NMAX = 5001 ;
const int GMAX = 10001 ;
ifstream cin ("rucsac.in") ;
ofstream cout ("rucsac.out") ;

int N, G ;
int W[NMAX], P[NMAX] ;
int Optim[GMAX] ;

int main()
{
    cin >> N >> G ;

    for(int i = 1 ; i<= N ; ++ i)
        cin >> W[i] >>  P[i] ;


    Optim[0] = 0 ;
    int sol = 0 ;

    for(int i = 1; i <= N ; ++ i)
        for(int j = G - W[i] ; j >= 0 ; -- j)
                if(Optim[j + W[i]] < Optim[j] + P[i])
                  {
                      Optim[j + W[i]] = Optim[j] + P[i] ;
                      if(Optim[j + W[i]] > sol)
                        sol = Optim[j + W[i]] ;
                  }

    cout << sol << '\n' ;
    cin.close() ;
    cout.close() ;
    return 0 ;
}