#include<fstream>

#define Nmax 5010
#define Num 10010

using namespace std;

int n, g, w[Nmax], p[Nmax], v1[Num], v2[Num];

int main()
{
    ifstream f("rucsac.in");
    ofstream h("rucsac.out");
    f >> n >> g;
    for (int i = 1; i <= n; ++i)
        f >> w[i] >> p[i];
    f.close();

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= g; ++j)
        {
            v2[j] = v1[j];
            if (w[i] <= j)
                v2[j] = max (v2[j], v1[j - w[i]] + p[i]);
        }
        for (int j = 0; j <= g; ++j)
        {
            v1[j] = v2[j];
        }
    }

    int maxim = 0;
    for (int i = 0; i <= g; ++i)
        if (maxim < v1[i])
            maxim = v1[i];
    h << maxim << '\n';

    h.close();
    return 0;
}