#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int i,j,n,w1;
	int v[100],w[100];
	int *temp,*last,*next;
	
	scanf("%d %d",&n,&w);
	for(i=0;i<n;i++) scanf("%d %d",v[i],w[i]);
	
	last=(int *)calloc(w1,sizeof(int));
	next=(int *)calloc(w1,sizeof(int));
	for(i=0;i<n;i++){
		for(j=0;j<w1;j++){
			if(j-w[i]>=0 && last[j-w[i]]+v[i]>last[j]) next[j]=last[j-w[i]]+v[i];
			else next[j]=last[j];
		}
		temp=last;
		last=next;
		next=temp;
	}
	printf("%d\n",last[i]);
	return 0;
}