#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ff                  first
#define ss                  second
#define int                 long long
#define pb                  push_back
#define mp                  make_pair
#define pii                 pair<int,int>
#define vi                  vector<int>
#define vvi                 vector< vi > 
#define vpii                vector< pair<int,int> > 
#define mii                 map<int,int>
#define pqb                 priority_queue<int>
#define pqs                 priority_queue<int,vi,greater<int> >
#define loop(i,a,b)         for(int i=a;i<b;i++)
#define LOOP(i,a,b)         for(int i=a;i<=b;i++)
#define looprev(i,a,b)      for(int i=a;i>=b;i--)
#define rloop(it,c)         for(auto& it : c)
#define sz(a)               a.size()
#define all(c)              c.begin(),c.end()
#define tr(i,c)             for(auto i = c.begin(); i != c.end(); i++)
#define present(c,x)        (c.find(x) != c.end())
#define cpresent(c,x)       (find(all(c),x) != c.end())
#define spresent(s,x)       (s.find(x) != s.npos)           //use 'x' while passing to parameters  ||  we can also use cpresent(c,x)
#define setbits(x)          __builtin_popcountll(x)
#define zrobits(x)          __builtin_ctzll(x)
#define SETINT(a,x)         memset(a, x, sizeof(a))
#define SETCHAR(str,x)      memset(str, x, sizeof(str)      //use 'x' while passing to parameters  
#define mod                 1000000007
#define inf                 1e18
#define ps(x,y)             fixed<<setprecision(y)<<x
#define w(x)                int x; cin>>x; while(x--)
mt19937                     rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
int fact(int n, int m=mod)
{
    int x = 1;
    LOOP(i,2,n)
    {
        x = (x*i)%m;
    }
    x = x%m;
    if (x < 0) x += m;
}
 
bool prime(int n)
{
    if (n < 2) 
        return false;
    for (int x = 2; x*x <= n; x++)
    {
        if (n%x == 0)
            return false;
    }
    return true;
}
 
vi factors(int n)
{
    vi f;
    for (int x = 2; x*x <= n; x++)
    {
        while (n%x == 0) 
        {
            f.pb(x);
            n /= x;
        }
    }
    if (n > 1) 
        f.pb(n);
    return f;
}
 
 
int raise(int a,int n,int m)
{
  
    if(n == 0)return 1;
    if(n == 1)return a;
    int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}
 
int floor1(int n,int k)
{
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}
 
int ceil1(int n,int k)
{
    return floor1(n+k-1,k);
}
 
 
void Gur27()
{
    ios::sync_with_stdio(0); cin.tie(0); 
 
}
 
int dp[101][100001];
 
int knapsack(int vl[],int wt[],int w,int n)
{
    if(n==0 || w==0)
        return 0;
    if(dp[n][w]!=-1)
        return dp[n][w];
    if(wt[n-1]<=w)
        return dp[n][w]=max(vl[n-1]+knapsack(vl,wt,w-wt[n-1],n-1),knapsack(vl,wt,w,n-1));
    else
        return dp[n][w]=knapsack(vl,wt,w,n-1);
    
}
 
 
int32_t main()
{
    Gur27();
    int N,W;
    cin>>N>> W;
    int val[N];
    int wt[N];
    loop(i,0,N)
    {
        cin>>wt[i];
        cin>>val[i];
        
    }
    SETINT(dp,-1);
    cout<<knapsack(val,wt,W,N)<<'\n';
    
    
    return 0;
}

Measured memory_bytes: 79232