#include <fstream>

using namespace std;

int n, g, w[5001], p[5001], v[5001][10001];

void read();
void solve();

int main()
{
    read();
    solve();
    return 0;
}

void read()
{
    freopen ( "rucsac.in", "r", stdin );
    scanf ( "%d%d", &n, &g );
    int x, y;
    for ( int i = 1; i <= n; ++i )
        scanf ( "%d%d", &x, &y ),
        w[i] = x, p[i] = y;
    fclose(stdin);
}

void solve()
{
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= g; ++j )
        {
            v[i][j] = v[i-1][j];
            if ( j >= w[i] )
                v[i][j] = max ( v[i-1][j], v[i-1][j-w[i]] + p[i] );
        }
    printf ( "%d\n", v[n][g] );
}