#include <cstdio>

using namespace std;

#define IN "rucsac.in"
#define OUT "rucsac.out"
#define G_MAX 10002

int D[G_MAX];
int W[G_MAX/2] , P[G_MAX/2];
int N , G;

int mx ( int a , int b )

{
    if ( a > b )    //functia maxim
        return a;
    else return b;
}

void Read()

{
    int i;

    scanf ( "%d%d" , &N , &G );//citim numarul de obiecte si greutatea maxima

    for ( i = 1 ; i <= N ; i ++ )
    {
        scanf ( "%d%d" , &W[i] , &P[i] );//citim greutatea si profitul la al i-lea obiect
    }

}
void Solve()

{
    int Mx = 0;
    int i , j;

    for ( i = 1 ; i <= N ; i ++ )
        for ( j = G ; j >= W[i] ; j -- )
            D[j] = mx( D[j] , D[j-W[i]] + P[i] );//comparam valoarea actuala cu valoarea care am obtine-o cu profitul obiectului cu greutatea j-W[i] + profitul greutatii actuale(P[i]) si alegem maximul

    for ( i = 1 ; i <= G ; i ++ )//cautam profitul maxim pe care l-am obtinut
       Mx = mx ( Mx , D[i] );



    printf ( "%d" , Mx );//afisam profitul maxim obtinut
}
int main()
{
    freopen ( IN , "r" , stdin );
    freopen ( OUT , "w" , stdout );

    Read();
    Solve();
}