#include<stdio.h>
#define max(a,b) ((a)>(b) ? (a):(b))
int N,W;
int v[100],w[100];
int dp[101][10001];
int rec(int i,int j){
    int res;
    if(dp[i][j]>=0) return dp[i][j];
    if(i==N) res=0;
    else if(j<w[i]) res=rec(i+1,j);
    else res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
    return dp[i][j]=res;
}

int main(void){
    int i,j;

    scanf("%d%d",&N,&W);
    for(i=0;i<N;i++){
	scanf("%d%d",&v[i],&w[i]);
    }
    for(i=0;i<=100;i++) for(j=0;j<=10000;j++) dp[i][j]=-1;
    printf("%d\n",rec(0,W));

    return 0;
}