#include<fstream>
#include<algorithm>
# define MAXN 10005
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int N,G,W[MAXN],P[MAXN],D[5001][MAXN];
int main() {
	  int i,cw;
	  cin>>N>>G;
	  for(i=1;i<=N;i++)
	       cin>>W[i]>>P[i];
	  for(i=1;i<=N;i++)
	   for(cw=0;cw<=G;cw++) {
	        D[i][cw]=D[i-1][cw];
	if (W[i]<=cw)
	 D[i][cw]=max(D[i][cw],D[i-1][cw-W[i]]+P[i]);
}
cout<<D[N][G];
return 0;
}