#include <fstream>

using namespace std;

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

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

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)
       best[j]=max(best[j],best[j-g[i]]+v[i]);
  }

  fout<<best[G];
}

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

    return 0;
}