#include<stdio.h>
#define TheD 5001
#define TheGD 10001

int n,W,w[TheD],v[TheD],d[TheGD],sol;


int main()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);

	scanf("%d %d",&n,&W);

	for(int i=1;i<=n;i++)
		scanf("%d%d",&w[i],&v[i]);

	for(int i=1;i<=n;i++)
		for(int j=W-w[i];j >= 0; j--)
			if( d[j+w[i]] < d[j]+v[i])
			{
				d[j+w[i]]=d[j]+v[i];
				if(d[j+w[i]]>sol)
					sol=d[j+w[i]];
			}
	printf("%d",sol);
}