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

 
int main()
{
  ifstream fin("rucsac.in");
  ofstream fout("rucsac.out");
  int N, G;
  int D[2][10000];
  for(int i=0;i<2;++i)
    for(int j=0;j<10000;++j)
      D[i][j]=0;
  vector <int> g,v;
  int a, b;
  fin >> N >> G;
  for(int i = 1; i <= N; ++i)
  {
    fin >> a >> b;
    g.push_back(a);
    v.push_back(b);
  }
  int p = 0;
  for(int i = 1; i <= N; ++i)
  {
    for(int j = 1; j <= G; ++j)
    {
      D[p][j] = D[!p][j];
      if(g[i - 1] <= j)
      {
        D[p][j] = max(D[p][j], D[!p][j - g[i - 1]] + v[i - 1]);
      }
    }
    p = !p;
  }
  fout << D[!p][G] << "\n";
  return 0;
}