#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mod 1000000007
const int N=200005;

ll modulo(ll num,ll MOD=mod){ return ((num%MOD)+MOD)%MOD;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),MOD-2,MOD); }

const int MAX=1e5;

int tree[4*MAX];
int lazy[4*MAX];
int arr[]={0,0,0,0,0,0};

void build(int node, int start, int end)
{
    if(start == end)
    {
        // Leaf node will have a single element
        tree[node] = arr[start];
    }
    else
    {
        int mid = (start + end) / 2;
        // Recurse on the left child
        build(2*node, start, mid);
        // Recurse on the right child
        build(2*node+1, mid+1, end);
        // Internal node will have the sum of both of its children
        tree[node] = max(tree[2*node], tree[2*node+1]);
    }
}

void updateRange(int node, int start, int end, int l, int r, int val)
{
    if(lazy[node] != 0)
    { 
        // This node needs to be updated
        tree[node] += lazy[node];    // Update it
        if(start != end)
        {
            lazy[node*2] += lazy[node];                  // Mark child as lazy
            lazy[node*2+1] += lazy[node];                // Mark child as lazy
        }
        lazy[node] = 0;                                  // Reset it
    }
    if(start > end or start > r or end < l)              // Current segment is not within range [l, r]
        return;
    if(start >= l and end <= r)
    {
        // Segment is fully within range
        tree[node] += val;
        if(start != end)
        {
            // Not leaf node
            lazy[node*2] += val;
            lazy[node*2+1] += val;
        }
        return;
    }
    int mid = (start + end) / 2;
    updateRange(node*2, start, mid, l, r, val);        // Updating left child
    updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
    tree[node] = max(tree[node*2], tree[node*2+1]);        // Updating root with max value 
}

int queryRange(int node, int start, int end, int l, int r)
{
    if(lazy[node] != 0)
    {
        // This node needs to be updated
        tree[node] += lazy[node];            // Update it
        if(start != end)
        {
            lazy[node*2] += lazy[node];         // Mark child as lazy
            lazy[node*2+1] += lazy[node];    // Mark child as lazy
        }
        lazy[node] = 0;                 // Reset it
    }
    if(start > end or start > r or end < l)
        return 0;         // Out of range
    if(start >= l and end <= r)             // Current segment is totally within range [l, r]
        return tree[node];
    int mid = (start + end) / 2;
    int p1 = queryRange(node*2, start, mid, l, r);         // Query left child
    int p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
    return max(p1, p2);
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
    cout<<fixed<<setprecision(15);
    
    int N,W;
    cin>>N>>W;

    ll wt[N], val[N];

    for(int i=0;i<N;i++) {
        cin>>wt[i]>>val[i];
    }

    ll dp[W+1][N+1];

    for(int i=0;i<W+1;i++) {
        for(int j=0;j<=N;j++) {
            dp[i][j]=0;
        }
    }

    for(int i=0;i<=W;i++) {
        for(int j=0;j<=N;j++) {
            if(i==0 || j==0) {
                dp[i][j]=0;
            }
            else if(wt[j-1]<=i) {
                dp[i][j]=max(dp[i][j-1], val[j-1]+dp[i-wt[j-1]][j-1]);
            }
            else {
                dp[i][j]=dp[i][j-1];
            }
        }
    }

    cout<<dp[W][N];
    
    return 0;
}

Measured memory_bytes: 79232