// ------- PBDS ------ //
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// ------- PBDS ------ //

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define testcase ll tt; cin>>tt; while(tt--)
#define pb push_back
#define nn cout<<"\n"
#define MOD 1000000007
#define pi 3.1415926535
#define endl "\n"
#define vll vector<ll>
#define MULTI int T; cin >> T; while(T--)
#define all(a)      (a).begin(),(a).end()
#define here cout<<"I'm here\n";
void vout(vector<ll> ans){
    for(auto ele:ans) cout<<ele<<" "; cout<<endl;
}
vector<ll> adj[200001];
bool vis[200001];

// ------- PBDS ------ //
typedef tree<
// change this for any data-type
string,
null_type,
// change this for any data-type
less<string>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

/*
    to get the position of an element in set , do
    s.order_of_key(ele);
    this returns the number of elements strictly lesser than ele in set s
    Let us assume we have a set s : {1, 5, 6, 17, 88}, then :
    s.order_of_key(6) : Count of elements strictly smaller than 6 is 2.
    s.order_of_key(25) : Count of elements strictly smaller than 25 is 4.

    to get the element at position k
    s.find_by_order(k);
    returns an iterator to the ele counting from 0
    Let us assume we have a set s : {1, 5, 6, 17, 88}, then :
    *(s.find_by_order(2)) : 3rd element in the set i.e. 6
    *(s.find_by_order(4)) : 5th element in the set i.e. 88
*/

// ------- PBDS ------ //

clock_t time_p=clock();
void purvansh11()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

//BINARY EXPONENTIATION  -- O(log2(b))
ll power(ll a, ll b) {
    /*
        for 3^11 :
        as 11 -> 1011, we mean 3^8 * 3^2 * 3^1
        so multiply for all ones in binary rep of b
    */

    ll ans = 1;
    ll num = a;
    while (b > 0) {
        if (b & 1) ans = ((ans % MOD) * (num % MOD)) % MOD;
        num = ((num % MOD) * (num % MOD)) % MOD;
        b /= 2;
    }
    return ans;
}
ll n,w;
vector<ll> wt,val;
ll dp[101][100001];
ll solve(ll i,ll w){
    if(i==n) return 0;

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

    if(w-wt[i]>=0){
        return dp[i][w] = max(val[i] + solve(i+1,w-wt[i]),solve(i+1,w));
    }
    else{
        return dp[i][w] = solve(i+1,w);
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    SPEED;
    cout.precision(8);
    cout << fixed;
    memset(dp,-1,sizeof(dp));
    cin>>n>>w;
    for(ll i=0;i<n;i++){
        ll a,b;
        cin>>a>>b;
        wt.pb(a);
        val.pb(b);
    }
    memset(dp,0,sizeof(dp));
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=w;j++){
            if(j>=wt[i-1])
                dp[i][j] = max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout<<dp[n][w];
    purvansh11();
    return 0;
}

Measured memory_bytes: 87396