#include <cstdio>

#define NMax 5002

using namespace std;

long mp[NMax];
long maxG, weight, price, g, n;

int main()
{
    freopen ( "rucsac.in", "r", stdin );
    freopen ( "rucsac.out", "w", stdout );

    scanf ( "%ld %ld", &n, &g );
    for ( long i = 1; i <= n; i++ ) {
        scanf ( "%ld %ld", &weight, &price );
        for ( long j = g - weight; j >= 0; j-- )
            if ( ( j == 0 || mp[j] ) && mp[j + weight] < mp[j] + price )
                mp[j + weight] = mp[j] + price;
    }

    for ( long i = 1; i <= g; i++ )
        if ( mp[i] > maxG )
            maxG = mp[i];

    printf ( "%ld\n", maxG );

    return 0;
}