#include <cstdio>

#define Nmax 5005
#define Gmax 10005

int N, G, W[Nmax], P[Nmax], DP[Gmax], Sol;

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

void Dinamica()
{
    for (int i = 1; i <= N; ++i)
    {
        for (int j = G - W[i]; j >= 0; --j)
        {
            if (DP[j + W[i]] < DP[j] + P[i])
            {
                DP[j + W[i]] = DP[j] + P[i];
                if (DP[j + W[i]] > Sol)
                    Sol = DP[j + W[i]];
            }
        }
    }
}

void Afisare()
{
    printf("%d", Sol);
}

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

    Citire();
    Dinamica();
    Afisare();

    return 0;
}