#include <cstdio>

int n, g, w[5001], p[5001], sol[10001], sf;

void Citire()
{
    FILE *F = fopen("rucsac.in", "r");
    fscanf(F, "%d%d", &n, &g);
    for (int i = 1; i <= n; ++i)
        fscanf(F, "%d%d", &w[i], &p[i]);
    fclose(F);
}

void Dinamica()
{
    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]] > sf)
                    sf = sol[j + w[i]];
            }
        }
    }
}

void Afisare()
{
    FILE *G = fopen("rucsac.out", "w");
    fprintf(G, "%d", sf);
}

int main()
{
    Citire();
    Dinamica();
    Afisare();
    return 0;
}