//
#include<stdio.h>
#include<stdlib.h>
FILE *f=fopen("rucsac.in","r"),*g=fopen("rucsac.out","w");
int n,suma,cost[5001],val[5001];
int i,j,k,s,opt[10001];


void read()
{
	fscanf(f,"%d %d",&n,&suma);
	
	for( i=1;i<=n;i++)
		fscanf(f,"%d %d",&cost[i],&val[i]);
}

void print()
{
	fprintf(g,"%d",s);
	fcloseall();
}


void solve()
{
	for(i=1;i<=n;i++)
		for(j=suma-cost[i];j>=0;j--)
		{
			if( opt[j+cost[i]] < opt[j] + val[i] )
			{
				opt[j+cost[i]]=opt[j]+val[i];

			if(opt[j+cost[i]]>s)
				s=opt[j+cost[i]];
		
			}
		}
}


int main()
{
	read();
	solve();
	print();

	return 0;
}