#include <fstream>
using namespace std;

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

const int NMAX = 5001;

int G[NMAX], P[NMAX], M[2][2 * NMAX],
    N, Gmax;

int main()
{
    f >> N >> Gmax;
    for(int i = 1; i <= N; i++)
        f >> G[i] >> P[i];
    int p = 0, u = 1;
    for(int i = 1; i <= N; i++)
    {
        for(int g = 0; g <= Gmax; g++)
        {
            M[u][g] = M[p][g];
            if(g - G[i] >= 0)
                M[u][g] = max(M[u][g], M[p][g - G[i]] + P[i]);
        }
        swap(p, u);
    }
    g << M[p][Gmax];
    return 0;
}