#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();

    v1[w[1]] = p[1];

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

    h << v2[g] << '\n';

    h.close();
    return 0;
}