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