#include <fstream>
#include <iostream>
using namespace std;

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

int N,G,Pmax;

int W[5005],P[5005],D[5][1005];

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]);
        }
    for(i=0;i<=G;++i)   D[1][i]=D[2][i];

    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]);
        }
      for(i=0;i<=G;++i)   D[1][i]=D[2][i];
    }
    Pmax=D[1][G];
    fout<<Pmax;
    return 0;
}