#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

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


#define    boost        ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define    nl           "\n"
#define    ll           long long
#define    pb           push_back
#define    mpr          make_pair
#define    fr(i,a,n)    for(ll i=a;i<n;++i)
#define    fr0(i,n)     for(ll i=0;i<n;++i)
#define    pii          pair<int, int>
#define    mem(a)       memset(a,0,sizeof(a))
const ll mod = 1000000007;

void fio()
{
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
}

template<typename T> void TIME(T start, T end)
{
#ifndef ONLINE_JUDGE
    double time_taken =  chrono::duration_cast<chrono::nanoseconds>(end - start).count();
    time_taken *= 1e-9;
    cout << "\nExecuted in: " << fixed
         << time_taken << setprecision(9);
    cout << " sec";
#endif
}


//BFS CODE===================================================================

const int N = 2e6 + 5;

vector<ll> adj[N];
bool visited[N];
ll val[N];
ll depth[N];
ll parent[N];


void clear_all() {
    for (auto& v : adj) {
        v.clear();
    }
    mem(visited);
    mem(val);
    mem(depth);
    mem(parent);
   
}


 
 
void bfs(ll s) {
    queue<ll> q;
    q.push(s);
    visited[s] = true;
    depth[s] = 0;
    while (!q.empty()) {
        ll v = q.front();
        q.pop();
        for (ll u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                parent[u] = v;
                q.push(u);
                depth[u] = depth[v] + 1;
            }
        }
    }
}


void dfs(ll v) {
    visited[v] = true;
    for (ll u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
}


// left shift << multiply by 2
// right shift >> divide by 2


//MODULAR EXPONENTION (pow(x,y)%p)=========================================================================
ll modexp(ll x, ll y, ll p)
{
    ll res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result; 
} 


bool sortinrev(const pair<ll,ll> &a,  
               const pair<ll,ll> &b) 
{ 
       return (a.first > b.first); 
} 

int main()
{
    auto start = chrono::high_resolution_clock::now();
    boost;
    fio();
    ll t = 1;
    // cin >> t;
    while (t--) {
     ll n,W;
     cin>>n>>W;
     ll w[n], v[n];
     fr0(i,n)
        cin>>w[i]>>v[i];

    ll dp[n+1][W+1];
    mem(dp);
    

    for(ll i=1; i<n+1; i++)
        for(ll j=1;j<W+1;j++){
            
            if(w[i-1]<=j){
                dp[i][j]= max( (v[i-1]+ dp[i-1][j-w[i-1]]) , dp[i-1][j]);
            }
            else
                dp[i][j]= dp[i-1][j];
                
        }
    cout<<dp[n][W];
  
       
    }
    auto end = chrono::high_resolution_clock::now();
    TIME(start, end);
    return 0;
}

Measured memory_bytes: 129416