#include<stdio.h>
#include<stdlib.h>
#define max(a,b) (a>b)?a:b
int main(void){
	int N,W,i,j;
	int *v,*w,*dp;
	scanf("%d%d",&N,&W);
	v=calloc(N,sizeof(int));
	w=calloc(N,sizeof(int));
	dp=calloc(W+1,sizeof(int));
	for(i=0;i<N;i++){scanf("%d%d",&v[i],&w[i]);}
	for(i=0;i<N;i++){
		for(j=w[i];j<=W;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	printf("%d\n",dp[W]);
	free(v);free(w);free(dp);
	return 0;
}