#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];
int DP[2][GX];
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,k,k1;
citeste();
k=1;k1=1;
for(i=1;i<=n;i++)
	{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];
				}
			}
		}
	if(k==1)
		{k=0;k1=-1;
		}
	else
		{k=1;k1=1;
		}
	}
if(k==0)
	{fprintf(gi,"%d",DP[1][GMAX]);
	}
else
	{fprintf(gi,"%d",DP[0][GMAX]);
	}
fclose(f);
fclose(gi);
return 0;
}