#include <cstdio>

#define NMAX 5005
#define GMAX 10005

int N, G, W[NMAX], P[NMAX], sol[GMAX];

void citire()
{
    scanf("%d %d", &N, &G);

    for (int i = 1; i <= N; ++i)
        scanf("%d %d", &W[i], &P[i]);
}

void rezolvare()
{
    int ans = 0;

    for (int i = 1; i <= N; ++i)
        for (int j = G - W[i]; j >= 0; --j)
        {
            if (sol[j + W[i]] < sol[j] + P[i])
                sol[j + W[i]] = sol[j] + P[i];
            if (sol[j + W[i]] > ans)
                ans = sol[j + W[i]];
        }
    printf("%d", ans);
}

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

    citire();
    rezolvare();

    return 0;
}