#include <fstream>

using namespace std;

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

int N,G;
int Gline;
int g[5001];
int v[5001];
int best[5001];
bool f[5001];

void Read()
{
  fin>>N>>G;

  for(int i=1; i<=N; ++i)
    fin>>g[i]>>v[i];

  fin.close();
}

void Do()
{
  for(int i=1; i<=N; ++i)
  {
    for(int j=G; j>=1; --j)
      if(g[i]<=j)
        if(best[j]<best[j-g[i]]+v[i])
         best[j]=best[j-g[i]]+v[i];
  }

  fout<<best[G];
}

int main()
{
   Read();
   Do();

    return 0;
}