#include <fstream>
#define nmax 5001
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,G,c[nmax][nmax];

struct obiect
{ int g;
  int C;

};
obiect a[nmax];
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<=n;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];
}

void solutie()
{ int x,y;
  x=n;
  y=G;
  while(c[x][y]!=0)
  if(c[x][y]!=c[x-1][y])  {   y=y-a[x].g; x--; }
  else x--;
}
int main()
{   citire();
    dinamica();
    solutie();
    fin.close();
    fout.close();
    return 0;
}