#include <stdio.h>
int main(){
	int N,W;//n:個数,w:容量
	scanf("%d %d",&N,&W);
	int v[N],w[N];//v:価値,w:重量
	int i,j;
	for(i=0;i<N;i++){
		scanf("%d %d",&v[i],&w[i]);
	}
	int temp;
	for(i=0;i<N;i++){//準バブルソート
		for(j=i+1;j<N;j++){
			if(w[i]>w[j]){
				temp=w[i];
				w[i]=w[j];
				w[j]=temp;
				temp=v[i];
				v[i]=v[j];
				v[j]=temp;
			}
		}
	}
	int dp[N][W+1];
	for(i=0;i<N;i++){
		for(j=0;j<=W;j++){
			dp[i][j]=0;
		}
	}
	int a;
	for(i=w[0];i<=W;i++){
		a=i/w[0];
		dp[0][i]=a*v[0];
	}
	for(i=1;i<N;i++){
		for(j=0;j<=W;j++){
			temp=0;
			if(j>=w[i]){
				a=j/w[i];
				temp=a*v[i] + dp[i-1][j-a*w[i]];
			}
			dp[i][j]=dp[i-1][j]>temp?dp[i-1][j]:temp;
		}
	}
	printf("%d\n",dp[N-1][W]);
	return 0;
}
	