#include<bits/stdc++.h>
using namespace std;
int n,m;
long long dp[40000001],a[500001],w[500001];
long long g;
int main(){
    freopen("Mining.in","r",stdin);
    freopen("Mining.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i],&w[i]);
        if(i==2)g=__gcd(w[1],w[2]);
        else if(i>2)g=__gcd(g,w[i]);
    }
    for(int i=1;i<=n;i++){
        w[i]/=g;
    }
    m/=g;
    for(int i=1;i<=n;i++){
        for(int k=m;k>=w[i];k--){
            dp[k]=max(dp[k],dp[k-w[i]]+a[i]);
        }
    }
    cout<<dp[m];
    fclose(stdin);
    fclose(stdout);
    return 0;
}