#include<stdio.h>
FILE *f=fopen("rucsac.in","r"),*gi=fopen("rucsac.out","w");
const int N=1002,GX=10001;
int w[N],p[N],DP[2][GX],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,k,k1;
citeste();
k=1;k1=1;
for(i=1;i<=n;i++,k=1-k,k1=k1*-1)
	{for(g=0;g<=GMAX;g++)
		{DP[k][g]=DP[k-k1*1][g];
		if(w[i]<=g)	
			{if(DP[k][g]<DP[k-k1*1][g-w[i]]+p[i])
				{DP[k][g]=DP[k-k1*1][g-w[i]]+p[i];
				}
			}
		}
	}
fprintf(gi,"%d",DP[1-k][GMAX]);
fclose(f);
fclose(gi);
return 0;
}