#include <cstdio>

using namespace std;

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

int n , G;
int D[10002][10002];
struct element
{
    int V,W;
}v[5003];

int maxim ( int a , int b )
{
    if ( a > b )

        return a;

        else return b;
}

void Read()
{
    int i;

    scanf ( "%d%d" , &n , &G );

    for ( i = 1 ; i <= n ; i ++ )

        scanf ( "%d%d" , &v[i].W , &v[i].V );
}

void Solve()
{
    int i , j;


    for ( i = 1 ; i <= G ; i ++ )

        D[0][i] = 0;

    for ( i = 1 ; i <= n ; i ++ )
        for ( j = 1 ; j <= G ; j ++ )
            if ( j >= v[i].W )
    {
        D[i][j] = maxim(D[i-1][j] , D[i-1][j-v[i].W] + v[i].V );
    }

            else D[i][j] = D[i-1][j];

        printf ( "%d" , D[n][G] );

       /* for ( i = 0 ; i <= n ; i ++ ){

            for ( j = 1 ; j <= G ; j ++ )

                printf ( "%d" , D[i][j] );

        printf ( "\n");}*/
}
int main()
{
    freopen ( IN , "r" , stdin );
    freopen ( OUT , "w" , stdout );

    Read();
    Solve();
}