#include <fstream>
#define MAX 5000
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int rucsac[MAX+5][MAX*2+5] , N , G , w , p;
int main()
{ fin >> N >> G;
  for(int i=1;i<=N;i++)
  { fin >> w >> p;
    for(int j=1;j<w;j++)
    rucsac[i][j]=rucsac[i-1][j];
    for(int j=w;j<=G;j++)
    rucsac[i][j]=max(rucsac[i-1][j-w]+p,rucsac[i-1][j]);
  }
  fout << rucsac[N][G] << '\n';
    return 0;
}