#include<fstream>
#define NMax 5007
#define GMax 10007

using namespace std;

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

int N,G,Pmax;

int W[NMax],P[NMax],D[5][GMax];

void sw()
{
    int i;

    for(i=0;i<=G;++i)   D[1][i]=D[2][i];

}

int main()
{
    int i,cw;

    fin>>N>>G;

    for(i=1;i<=N;++i)
    {
        fin>>W[i]>>P[i];
    }

    for(cw = 0; cw <= G; ++cw)
        {
            D[2][cw] = D[1][cw];

            if(W[1] <= cw)
                D[2][cw] = max(D[2][cw], D[1][cw - W[1]] + P[1]);
        }
        sw();

    for(i = 2; i <= N; ++i)
    {
        for(cw = 0; cw <= G; ++cw)
        {
            if(W[i] <= cw)
                D[2][cw] = max(D[2][cw], D[1][cw - W[i]] + P[i]);
        }
        sw();
    }

    Pmax=D[1][G];

    fout<<Pmax<<"\n";

    fin.close();
    fout.close();
    return 0;
}