#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
//                 _Godspeed Rebels___
//                  _.' :  `._
//              .-.'`.  ;   .'`.-.
//     __      / : ___\ ;  /___ ; \      __
//   ,'_ ""--.:__;".-.";: :".-.":__;.--"" _`,
//   :' `.t""--.. '<@.`;_  ',@>` ..--""j.' `;
//       `:-.._J '-.-'L__ `-- ' L_..-;'
//          "-.__ ;  .-"  "-.  : __.-"
//              L ' /.------.\ ' J
//               "-.   "--"   .-"
//              __.l"-:_JL_;-";.__
//           .-j/'.;  ;""""  / .'\"-.
//         .' /:`. "-.:     .-" .';  `.
//      .-"  / ;  "-. "-..-" .-"  :    "-.
//   .+"-.  : :      "-.__.-"      ;-._   \
//   ; \  `.; ;                    : : "+. ;
//   :  ;   ; ;                    : ;  : \:
//  : `."-; ;  ;                  :  ;   ,/;
//   ;    -: ;  :                ;  : .-"'  :
//   :\     \  : ;             : \.-"      :
//   ;`.    \  ; :            ;.'_..--  / ;
//   :  "-.  "-:  ;          :/."      .'  :
//      \       .-`.\        /t-""  ":-+.   :
//       `.  .-"    `l    __/ /`. :  ; ; \  ;
//         \   .-" .-"-.-"  .' .'j \  /   ;/
//          \ / .-"   /.     .'.' ;_:'    ;
//           :-""-.`./-.'     /    `.___.'
//                 \ `t  ._  /  bug :F_P:
//                  "-.t-._:'
                 
//       _==/          i     i          \==_
//      /XX/            |\___/|            \XX\
//   /XXXX\            |XXXXX|            /XXXX\
//   |XXXXXX\_         _XXXXXXX_         _/XXXXXX|
//  XXXXXXXXXXXxxxxxxxXXXXXXXXXXXxxxxxxxXXXXXXXXXXX
// |XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// |XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
//  XXXXXX/^^^^"\XXXXXXXXXXXXXXXXXXXXX/^^^^^\XXXXXX
//   |XXX|       \XXX/^^\XXXXX/^^\XXX/       |XXX|
//     \XX\       \X/    \XXX/    \X/       /XX/
//       "\       "      \X/      "      /"
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define loop0 for(ll i=0;i<n;i++) 
#define loop1 for(ll i=1;i<=n;i++)
#define loopr0 for(ll i=n-1;i>=0;i++)
#define fst first 
#define mod 1000000007
#define maxs 1000005
#define se second 
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
#define pll pair <ll, ll>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
inline ll add(ll a, ll b){return ((a+b)<mod ? (a+b) : (a+b-mod) );}
int prime[maxs];
void seive()
{
       prime[0]=prime[1]=1;
       for(int i=2;i<=sqrt(maxs);i++)
       {
              if(prime[i])continue;
              for(int j=2*i;j<=maxs;j+=i)
              {
                     prime[j]=1;
              }
       }
}
inline ll sub(ll a , ll b){return ((a-b)<0?a-b+mod : a-b);}
ll power(ll a , ll b)
{
       if(b==0) return 1;
       ll y = power(a , b/2);
       y = (y*y)%mod;
       if(b&1) y = (a*y)%mod;
       return y;
}
using namespace std;

// End of Template Real work begins 

int main()
{
    ll n,wt;
    cin>>n>>wt;
    ll w[n+1],v[n+1];
    loop1{
        cin>>w[i]>>v[i];
    }
    ll dp[n+1][wt+1]={0};
    for(ll i=0;i<=n;i++)
    {
        for(ll j=0;j<=wt;j++)
        {
            if(i==0||j==0)
            dp[i][j]=0;
            else{
                if(w[i]>j)
                {
                    dp[i][j]=dp[i-1][j];
                }
            else
            dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]);
            }
          
        }
      
        
    }
    cout<<dp[n][wt]<<endl;
    
}

Measured memory_bytes: 82320