#include <stdio.h>

int a[3][13000]={0};//先前13000一直写成12800了！竟然一直没发现！

int main()
{
int n,m,v[13000],w[13000],i,j;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=1;i<=n;i++)
	scanf("%d%d",&w[i],&v[i]);
for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
		{
		if(w[i]>j) a[i%2][j]=a[(i-1)%2][j];
		else if(a[(i-1)%2][j-w[i]]+v[i]>a[(i-1)%2][j]) a[i%2][j]=a[(i-1)%2][j-w[i]]+v[i];
		else a[i%2][j]=a[(i-1)%2][j];
		}
printf("%d\n",a[n%2][m]);
}
return 0;
}