#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
#define countof(a) (sizeof(a)/sizeof((a)[0]))
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define bzero(p, n) memset(p, 0, n)
#define all(a) begin(a),end(a)
template<class T> inline void sort_uniq(T& c) { sort(ALL(c)); c.erase(unique(ALL(c)), c.end()); }
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class K, class V> void cout_v(map<K, V>& m)
{ for(auto it=m.begin();it!=m.end();it++)cout<<it->first<<":"<<it->second<<endl;}
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
inline int powi(int x,int y) {int p=1; while(y--) p*=x; return p;}
inline ll powll(ll x,ll y) {ll p=1; while(y--) p*=x; return p;}
template<class T> inline bool is_overlap(const T& a, const T& b, const T& p, const T& q)
{ return p <=b && a <= q; }
#define MOD = 1000000007;
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 

const ll N_MAX = 100;
const ll W_MAX = 1e5;
ll N, W;
ll dp[N_MAX + 1][W_MAX + 1];
ll w[N_MAX];
ll v[N_MAX];
ll memo[N_MAX][W_MAX];

ll knapsack(ll n_cur, ll w_cur)
{
    // cout << "knapsack(" << FMT2(_n, _w) << endl;
    ll value = 0;

    if (n_cur == N - 1) {
        if (w_cur + w[n_cur] <= W)
            value = v[n_cur];
    } else {
        value = knapsack(n_cur + 1, w_cur);
        if (w_cur + w[n_cur] <= W)
            chmax(value, knapsack(n_cur + 1, w_cur + w[n_cur]) + v[n_cur]);
    }
    // cout << FMT(r) << endl;
    return value;
}

ll knapsack_memo(ll n_cur, ll w_cur)
{
    if (memo[n_cur][w_cur] != -1)
        return memo[n_cur][w_cur];
    
    // cout << "knapsack(" << FMT2(_n, _w) << endl;
    ll value = 0;

    if (n_cur == N - 1) {
        if (w_cur + w[n_cur] <= W)
            value = v[n_cur];
    } else {
        value = knapsack(n_cur + 1, w_cur);
        if (w_cur + w[n_cur] <= W)
            chmax(value, knapsack(n_cur + 1, w_cur + w[n_cur]) + v[n_cur]);
    }
    // cout << FMT(r) << endl;
    return memo[n_cur][w_cur] = value;
}

// チーター本の2番目のコード
//  すっきりしてるけどおかしな結果を返す
ll knapsack_cheetah2(ll _n, ll _w)
{
    // cout << "knapsack(" << FMT2(_n, _w) << endl;
    if (_w > W) return -1;
    if (_n >= N) return 0;
    ll r = max(
        knapsack_cheetah2(_n + 1, _w),
        knapsack_cheetah2(_n + 1, _w + w[_n]) + v[_n]        
    );
    // cout << FMT(r) << endl;
    return r;
}

void cout_dp()
{
    rep(i, N+1) {
        rep(j,W+1) {
            cout << setw(3) << dp[i][j] << " ";
        }
        cout << endl;
    }
}

ll knapsack_dp()
{
    bzero(dp, sizeof(dp));

    rep(i, N) {
        rep(j, W + 1) {
            // cout << FMT4(i, j, w[i], v[i]) << endl;
            chmax(dp[i + 1][j], dp[i][j]);
            if (j + w[i] <= W)
                chmax(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
        }
        // cout_dp();
    }
    return dp[N][W];
}

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    memset(memo, -1, sizeof(memo));
    cin >> N >> W;
    // cout << FMT2(N,W) << endl;
    rep(i, N) cin >> w[i] >> v[i];
    ll ans;
    
    // ans = knapsack(0, 0);
    //ans = knapsack_memo(0, 0); // TLE
    // ans = knapsack_cheetah2(0, 0);
    ans = knapsack_dp();

    cout << ans << endl;
}



Measured memory_bytes: 157312