#include <iostream>
#include <fstream>

using namespace std;

const int NMAX=5000,
          GMAX=10000;

int W[NMAX+1], P[NMAX+1];
int D[GMAX+1];

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

int main()
{
    int N, G, Pmax=0, i;
    f>>N>>G;
    for(i=1; i<=N; ++i)
        f>>W[i]>>P[i];
    /// D[0]=0;
    for(i=1; i<=N; i++)
        for(int g=G-W[i]; g>=0; --g)
    {
        int cw=g+W[i],
            cp=D[g]+P[i];
            if(D[cw]<cp)
            {
                D[cw]=cp;
                if(cp>Pmax)
                    Pmax=cp;
            }
    }
    g<<Pmax;
    f.close();
    g.close();
    return 0;
}