#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
# define M_PIl          3.141592653589793238462643383279502884L /* pi */
# define int long long
//----------------------------------------------------------------------------------------------------
//gcd
ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
} 
//----------------------------------------------------------------------------------------------------
//modular exponentition
ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or  
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
}
//----------------------------------------------------------------------------------------------------
//segment tree
vector<ll> t;
void build(vector<ll> &a,ll v, ll tl, ll tr)
{
    if (tl == tr)
    {
        t[v] = a[tl];
    }
    else
    {
        ll tm = (tl+tr)/2;
        build(a,2*v,tl,tm);
        build(a,2*v+1,tm+1,tr);
        t[v] = t[2*v] + t[2*v+1];
    }
}
void update(ll v, ll tl, ll tr, ll pos, ll value)
{
    if (tl == tr)
    {
        t[v] = value;
    }
    else
    {
        ll tm = (tl+tr)/2;
        if (pos<=tm)
        {
            update(2*v,tl,tm,pos,value);
        }
        else
        {
            update(2*v+1,tm+1,tr,pos,value);
        }
        t[v] = t[2*v] + t[2*v+1];
    }
}
ll sum(ll v, ll tl, ll tr, ll l, ll r)
{
    if (r<l)
        return 0;
    if (tl == l && tr == r)
    {
        return t[v];
    }
    ll tm = (tl+tr)/2;
    return sum(2*v,tl,tm,l,min(r,tm)) + sum(2*v+1,tm+1,tr,max(l,tm+1),r);
}
//----------------------------------------------------------------------------------------------------
//Build Sieve
void sieveOfEratosthenes(ll N, vector<ll> &s) 
{ 
    // Create a boolean array "prime[0..n]" and 
    // initialize all entries in it as false. 
    vector <bool> prime(N+1, false); 
  
    // Initializing smallest factor equal to 2 
    // for all the even numbers 
    for (ll i=2; i<=N; i+=2) 
        s[i] = 2; 
  
    // For odd numbers less then equal to n 
    for (ll i=3; i<=N; i+=2) 
    { 
        if (prime[i] == false) 
        { 
            // s(i) for a prime is the number itself 
            s[i] = i; 
  
            // For all multiples of current prime number 
            for (ll j=i; j*i<=N; j+=2) 
            { 
                if (prime[i*j] == false) 
                { 
                    prime[i*j] = true; 
  
                    // i is the smallest prime factor for 
                    // number "i*j". 
                    s[i*j] = i; 
                } 
            } 
        } 
    } 
}
//--------------------------------------------------------------------
ll min_(ll a, ll b, ll c)
{
    return min(a,min(b,c));
}
ll max_(ll a, ll b, ll c)
{
    return max(a,max(b,c));
}
//--------------------------------------------------------------------
void dfs(ll u, vector<vector<ll>> &graph, vector<ll> &visited)
{
    visited[u] = 1;
    for (ll i=0;i<graph[u].size();i++)
    {
        if (visited[graph[u][i]] == 0)
        {
            dfs(graph[u][i],graph,visited);
        }
    }
}
//--------------------------------------------------------------------

int32_t main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,w,i,j;
    cin >> n >> w;
    //dprow->index, dpcol->rem_weight, dp[i][j] -> maxvalue upto index i and rem_weight j
    ll dp[n][w+1];
    memset(dp,0,sizeof(dp));
    ll weight[n];
    ll value[n];
    for (i=0;i<n;i++)
    {
        cin >> weight[i] >> value[i];
    }
    for (j=weight[0];j<=w;j++)
    {
        dp[0][j] = value[0];
    }
    for (i=1;i<n;i++)
    {
        for (j=1;j<=w;j++)
        {
            if (j-weight[i] < 0)
            {
                dp[i][j] = dp[i-1][j];
            }
            else
            {
                dp[i][j] = max(dp[i-1][j],value[i] + dp[i-1][j-weight[i]]);
            }
        }
    }
    /*for (i=0;i<n;i++)
    {
        for (j=0;j<=w;j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/
    cout << dp[n-1][w];
}


















Measured memory_bytes: 78336