#include <iostream>
#include <fstream>
#define MAXN 5010
#define MAXG 10010

using namespace std;

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

int N , G , PROFIT ;
int W[MAXN] , P[MAXN] ;
int Optim [ MAXG ] ;

void Citire ()
{
    fin >> N >> G ;
    for ( int i = 1 ; i <= N ; ++ i )
            fin >> W [i] >> P [i] ;
}

void Rucsac ()
{
    // Dinamica O ( G ) memorie
    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] ] ;
            }
        }
    fout << sol ;
}
int main()
{
    Citire () ;
    Rucsac () ;
    return 0;
}