//                    *** Author: Piyush Anand ***
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef  long long  int ll;
#define PI 3.14159265
#define pii pair<ll,ll>
#define ff first
#define ss second
#define mm " "
#define frev for(ll i=n-1;i>=0;i--)
#define inloop for(ll i=0;i<n;i++)cin>>a[i];
#define fa(x,v) for(auto x:v)
#define MM " "
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define f0 for(ll i=0;i<n;i++)
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define max4(a,b,c,d) max(a,max3(b,c,d))
#define f1 for(ll i=1;i<=n;i++)
#define VP vector< pii >
#define Sort(v) sort(v.begin(),v.end())
#define test ll T;cin>>T;while(T--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define pb push_back
#define pr cout<<'\n'
 const ll MOD=1000000000+7;
const ll MOD1 = 998244353;
#define vec vector<ll>
#define vecs vector<string>
#define min4(a,b,c,d) min(a,min3(b,c,d))
#define lb(v,val)  (lower_bound(v.begin(),v.end(),val)-v.begin())
#define ub(v,val)  (upper_bound(v.begin(),v.end(),val)-v.begin())
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
 
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
 
}
 

ll strTo(string s)
{
    stringstream tmp(s); 
    ll x = 0; 
    tmp >> x; 
 
return x;
}
 
string NoTo(ll n)
{
    ostringstream str1; 
    str1 << n; 
    string ans = str1.str();
    return ans; 
}


vector<bool>sieve(1000000,true);
void Sieve(){
 sieve[0]=false;
 sieve[1]=false;
 for(ll i=2;i*i<=1000000;i++){
  if(sieve[i]==true){
   for(ll j=i*i;j<1000000;j+=i)
    sieve[j]=false;
  }
 }
}
 
  ll lcm(ll a, ll b)  
 {  
    return (a*b)/gcd(a, b);  
 }  


ll arrlcm(ll arr[], ll n) 
{ 
    // Initialize result 
    ll ans = arr[0]; 
  
    // ans contains LCM of arr[0], ..arr[i] 
    // after i'th iteration, 
    for (ll i = 1; i < n; i++) 
        ans = (((arr[i] * ans)) / 
                (gcd(arr[i], ans))); 
  
    return ans; 
} 

ll arrgcd(ll arr[], ll n) 
{ 
    ll result = arr[0]; 
    for (ll i = 1; i < n; i++) 
    { 
        result = gcd(arr[i], result); 
  
        if(result == 1) 
        { 
           return 1; 
        } 
    } 
    return result; 
} 




ll nCr(ll n, ll r) 
{ 
    ll ans=1;
    f(i,0,r)
    {
        ans*=n-i;
        ans/=i+1;
    }
    return ans;
    

     
} 


ll fact(ll n)
{
    if (n == 0)
        return 1;
    return n * fact(n - 1);
}

vec v; 
void Divisors(ll n)
{
    for (ll i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
 
            if (n/i == i)
               v.pb(i);
            else 
                {
                    v.pb(i);
                    v.pb(n/i);
                }
        }
       
    }
}

 
ll no_of_divisors(ll n){ 
 ll c = 0; 
 for (ll i = 1; i <= sqrt(n); i++) { 
  if (n % i == 0){ 
   if(n/i==i)
    c=c+1;
   else
    c=c+2;
  }
 }
 return c; 
} 

 ll pwrn(ll x,ll y){ 
 if (y == 0) 
  return 1; 
 else if (y % 2 == 0) 
  return pwrn(x, y / 2) * pwrn(x, y / 2); 
 else
  return x * pwrn(x, y / 2) * pwrn(x, y / 2); 
}

 
 ll pwr(ll a, ll b){
 ll res=1;
 while(b>0){
  if(b&1)
   res=res*a;
  a*=a;
  b>>=1;
 }
 return res;
}
 
ll pwrm(ll a, ll b, ll m){
 a%=m;
 ll res=1;
 while(b>0){
  if(b&1)
   res=res*a%m;
  a=a*a%m;
  b>>=1;
 }
 return res;
}


ll digits(ll n)
{
    ll x = floor(log10(n)) + 1;
    return x;
}

vec prf;
void primeFactors(ll n)  
{  
    if(n%2==0)
    prf.pb(2);
    while (n % 2 == 0)  
    {  
      //  cout << 2 << " ";  
        n = n/2;  
    }  

    for (ll i = 3; i <= sqrt(n); i = i + 2)  
    {  
        // While i divides n, print i and divide n  

        if(n%i==0)
        prf.pb(i);
        while (n % i == 0)  
        {  
          //  cout << i << " ";  
            n = n/i;  
        }  
    }  
    if (n > 1)  
        prf.pb(n);
}  



/***************************************************************
 ***************************************************************
 **************************************************************/

ll n;
ll dp[110][100010];
 
ll knap(ll wt[],ll v[],ll w,ll n)
{
    if(w<=0||n<=0)
    return 0;

    if(dp[n][w]!=-1)
    return dp[n][w];

    if(wt[n]>w)
    return dp[n][w]=knap(wt,v,w,n-1);

    else
    {
        return dp[n][w]=max(v[n]+knap(wt,v,w-wt[n],n-1),knap(wt,v,w,n-1));
    }
    

}


int main()
{
  //system_testing_band_karo     
   fast;
    ll w;
   cin>>n>>w;
   ll wt[n+1];
   ll va[n+1];
    f(i,1,n+1)
    cin>>wt[i]>>va[i];

    f(i,0,n+1)
    {
        f(j,0,w+1)
    dp[i][j]=-1;}
    ll ans=knap(wt,va,w,n);

    cout<<ans<<"\n";
    


   
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
   return 0;

}



/*






 



 ll n;
   cin>>n;
   ll a[n];
    ll ctr=0;
   f(i,0,n)
   {
       cin>>a[i];
    //    if(a[i]==1)
    //    ctr++;
   }

   ll lo=0,hi=1;
   ll ma=-1,len=0,diff=0,ct=0,tp;
  f(i,1,n)
  {
      if(a[i]!=a[i-1]&&ct==0)
      {
          tp=a[i];
          ct++;
      }
      if(a[i]>a[i-1])
      diff;
      else if(a[i]<a[i-1])
      diff--;
      len++;
      if(diff>1||diff<-1)
      {
          if(len-lo>ma)
          ma=len-lo;

        lo=tp;
        ct=0;

      }
  }

  cout<<ma<<"\n";
 



*/


Measured memory_bytes: 82808