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