#include<stdio.h>
FILE *f=fopen("rucsac.in","r"),*gi=fopen("rucsac.out","w");
const int N=5000,G=10000;
int w[N],p[N];
int DP[N][G];
int n,GMAX;
void citeste()
{int i;
fscanf(f,"%d%d",&n,&GMAX);
for(i=1;i<=n;i++)
	{fscanf(f,"%d%d",&w[i],&p[i]);
	}
}
int main()
{int i,g;
citeste();
for(i=1;i<=n;i++)
	{for(g=0;g<=GMAX;g++)
		{DP[i][g]=DP[i-1][g];
		if(w[i]<=g)	
			{if(DP[i][g]<DP[i-1][g-w[i]]+p[i])
				{DP[i][g]=DP[i-1][g-w[i]]+p[i];
				}
			}
		}
	}
fprintf(gi,"%d",DP[n][GMAX]);
fclose(f);
fclose(gi);
return 0;
}