#include <fstream>

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

int n,G,c[5001][5001];
struct obiect
{ int c,g;};

obiect a[5001];
void citire()
{ int i;
  fin>>n>>G;
  for(i=1; i<=n; ++i)
      fin>>a[i].g>>a[i].c;
}

void dinamica()
{ int i,j;
  for(i=0; i<=G; ++i)
      c[0][i]=0;
  for(j=0; j<=G; ++j)
      c[j][0]=0;
  for(i=1; i<=n; ++i)
      for(j=1; j<=G; ++j)
          if(a[i].g>j) c[i][j]=c[i-1][j];
          else c[i][j]=max(c[i-1][j],a[i].c+c[i-1][j-a[i].g]);
  fout<<c[n][G];
}
int main()
{ citire();
  dinamica();
    return 0;
}