#include<fstream>
#include<cstring>

#define Nmax 5005
#define Wmax 10005

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

int W[Nmax], P[Nmax], D[Wmax], D2[Wmax];

int main()
{
    int N, G, sol = 0;
    in >> N >> G;

    for (int i = 1; i <= N; i++)
        in >> W[i] >> P[i];

    memset(D, -1, sizeof(D));
    D[0] = 0;

    for (int i = 1; i <= N; i++)
    {
        for (int j = G; j >= 0; j--)
            if (j - W[i] >= 0 && D[j - W[i]] != -1 && D[j - W[i]] + P[i] > D2[j])
                D2[j] = D[j - W[i]] + P[i];

        for (int j = 0; j <= G; j++)
            D[j] = D2[j];
    }
    for (int i = 0; i <= G; i++)
        if (D[i] > sol) sol = D[i];

    out << sol << "\n";
}