#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
 
#define ll long long int
#define ld long double
#define bigint int64_t
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define pb push_back
#define MOD 1000000007
#define flash ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(v) v.begin(),v.end()
#define pll pair<ll,ll>
#define test          int t;cin>>t;while(t--)
#define umi        unordered_map<int,int>
#define maxheap    priority_queue<int>
#define minheap    priority_queue<int,vector<int>,greater<int> >
#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 INF (ll)(1e18)
#define vvll vector<vector<ll>>
#define deb(x) cout<<#x<<" "<<x<<"\n" 
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
/*#include <ext/pb_ds/assoc_container.hpp> // Policy_based_Data_Structure 
#include <ext/pb_ds/graph_policy.hpp> 
using namespace __gnu_pbds;*/ 
 
#define forn(i,n) for(ll (i) = 0 ; (i) < (n) ; ++(i))
#define for1(i,n) for(ll (i) = 1 ; (i) <= (n) ; ++(i))
#define forr(i,n) for(ll (i) = (n)-1 ; (i)>=0 ; --(i))
#define forab(i,a,b,c) for(ll (i) = a ; (i) <= (b) ; (i)+=(c))
 
using namespace std;
template <typename T>
void read(T &x){
    cin >> x;
}
template <typename T , typename T0>
void read(T &x,T0 &y){
    cin >> x >> y;
}
 
template <typename T , typename T0 , typename T1>
void read(T &x,T0 &y,T1 &z){
    cin >> x >> y >> z;
}
 
template <typename T , typename T0 , typename T1 , typename T2>
void read(T &x,T0 &y,T1 &z,T2 &w){
    cin >> x >> y >> z >> w;
}
 
template <typename T , typename T0>
void read(pair< T , T0 > &p){
    cin >> p.fst >>p.scd;
}
 
template <typename T>
void read(vector< T > &oneD,ll n){
    forn(i,n)
    {
        ll x;
        read(x);
        oneD.push_back(x);
    }
}
 
template <typename T>
void read(T oneD[] , ll n){
    for(ll i=0;i<n;i++){
        read(oneD[i]);
    }
}
 
template <typename T>
void write(T &x){
    
    cout << x << " ";
}
 
template <typename T , typename T0>
void write(T &x,T0 &y){
    cout << x << " " << y << "\n";
}
 
template <typename T , typename T0 , typename T1>
void write(T &x,T0 &y,T1 &z){
    cout << x << " " << y << " " << z << "\n";
}
 
template <typename T , typename T0 , typename T1 , typename T2>
void write(T &x,T0 &y,T1 &z,T2 &w){
    cout << x << " " << y << " " << z << " " << w << "\n";
}
 
template <typename T , typename T0>
void write(pair< T , T0 > &p){
    write(p.fst);
    write(p.scd);
    cout << endl;
}
 
template <typename T>
void write(vector< T > &oneD){
    for(ll i=0;i<oneD.size();i++){
        write(oneD[i]);
    }
    cout << endl;
}
 
template <typename T>
void write(T oneD[] ,int n){
    for(ll i=0;i<n;i++){
        write(oneD[i]);
    }
    cout << endl;
}
 
template <typename T , typename T0>
void write(map< T , T0 > &mpp){
    for(auto it : mpp){
        write(it.fst);
        cout << ": ";
        write(it.scd);
        cout << "\n";
    }
    cout<<endl;
}
 
vll seive;
void Seive(){
    const ll maxn = 3000005;
    seive.resize(maxn);
    forn(i,maxn) seive[i] = i;
    seive[1] = -1;
    seive[0] = -1;
    forab(i,2,maxn,1) if(i == seive[i]) for(ll j = 2*i ; j < maxn ; j+=i) if(seive[j] == j) seive[j] = i;
}
 
ll extended_GCD(ll a , ll b , ll &x , ll &y){
    if(a == 0){
        x = 0;
        y = 1;
        return b;
    }
    ll x1 , y1;
    ll gcd = extended_GCD(b%a , a , x1 , y1);
    x = y1 - (b/a)*x1; 
    y = x1;
    return gcd;
}
 
long long moduloMultiplication(long long a, 
                            long long b, 
                            long long mod) 
{ 
    long long res = 0; // Initialize result 
  
    // Update a if it is more than 
    // or equal to mod 
    a %= mod; 
  
    while (b) 
    { 
        // If b is odd, add a with result 
        if (b & 1) 
            res = (res + a) % mod; 
  
        // Here we assume that doing 2*a 
        // doesn't cause overflow 
        a = (2 * a) % mod; 
  
        b >>= 1; // b = b / 2 
    } 
  
    return res; 
} 
ll modinv(ll a , ll mod = MOD){
    ll x , y,g;
    g=extended_GCD(a , mod , x , y);
    if(g!=1)
        return -1;
    else
    {
    if(x < 0) x += mod;
    return x;
}}
 
//Chinese Remainder Theoram
ll find_x_CRT(ll num[],ll rem[],ll n)
{
    ll pro=1;
    forn(i,n)
    pro*=num[i];
    ll res=0;
    forn(i,n)
    {
        ll pp = pro/num[i];
        res+=(rem[i]*modinv(pp,num[i])*pp);
    }
    res%=pro;
    return res;
}
 
ll power(ll a, ll b, ll m = MOD) {
    a%=m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a %m;
        a = a * a %m;
        b >>= 1;
    }
    return res;
}
 
 
ll po(ll a, ll b, ll m = MOD) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
 
ll gcd(ll a, ll b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
string getString(char x) 
{ 
    string s(1, x); 
    return s;    
} 
 
//typedef graph<ll, null_type, less<ll>, rb_graph_tag,graph_order_bigsmallistics_node_update> index_set
 
//Graph basic template
const ll maxn = 2e5+5;
void add_edge(ll u,ll v,vector<vll> &ad,ll a[],vector<ll> &fin)
{
    ad[u].pb(v);
    ad[v].pb(u);
    ll w1 = max(0LL,a[u]);
    ll w2 = max(0LL,a[v]);
    fin[u]+=w2;
    fin[v]+=w1;
}
string itos(ll s)
{
string str=to_string(s);
return str;
}
// Weighted Graph
/*vector<vector<pair<ll,ll>>> ad(maxn);
vector<bool> vis(maxn);
void add_edge(ll u,ll v,ll w)
{
    ad[u].pb({v,w});
    ad[v].pb({u,w});
}*/
void update(vll &BIT,ll index,ll inc)
{
    while(index<=BIT.size())
    {
        BIT[index]+=inc;
        index+=(index&(-index));
    }
}
 
ll query(vll &BIT,ll index)
{
    ll sum=0;
    while(index>0)
    {
        sum+=BIT[index];
        index-=(index&(-index));
    }
    return sum;
}
void precompute_NCR(vll &fact)
{
    const ll N = 1e6+5;
    fact[0] = 1;
    forab(i,1,(N-1),1)
    {
        ll y = (i%MOD*fact[i-1]%MOD)%MOD;
        fact[i] = y;
    }
}
 
ll NCR(vll &fact,ll N,ll R,ll mod=MOD)
{
    ll n = fact[N];
    ll r = fact[R];
    ll n_r = fact[N-R];
    ll y = (r%mod*n_r%mod)%mod;
    ll z = modinv(y,mod);
    ll ans = (n%mod*z%mod)%mod;
    return ans;
}
 
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> index_set; 
/*typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;*/

vll wt,val;
vvll dp;
ll n,w;
ll rec(ll w,ll pos){
    if(pos>=n) return 0;
    if(w-wt[pos]<0) 
        return dp[w][pos]=rec(w,pos+1);
    if(dp[w][pos]!=-1) return dp[w][pos];
    return(
        dp[w][pos]=max(rec(w-wt[pos],pos+1)+val[pos],rec(w,pos+1))
        );
}
int main()
{ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read(n,w);
wt=val=vll(n);
dp=vvll(w+1,vll(n,-1));
forn(i,n){
    read(wt[i],val[i]);
}
cout<<(rec(w,0));
}

Measured memory_bytes: 82304