#include <stdio.h>

#define NMAX 5000
#define GMAX 10000

struct object {
    unsigned weight, profit;
} Object[NMAX + 1];

unsigned long DP[NMAX + 1][GMAX + 1];

int main(void)
{
    unsigned i, n, G, g, l = 1;

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

    scanf("%u %u", &n, &G);
    for (i = 1; i <= n; i++)
        scanf("%u %u", &Object[i].weight, &Object[i].profit);

    for (i = 1; i <= n; i++, l = 1 - l)
        for (g = 0; g <= G; g++) {
            DP[l][g] = DP[1 - l][g];
            if (Object[i].weight <= g && DP[1 - l][g - Object[i].weight] + Object[i].profit > DP[l][g])
                DP[l][g] = DP[1 - l][g - Object[i].weight] + Object[i].profit;
        }

    printf("%lu\n", DP[n % 2][G]);

    return 0;
}