/*
    Author: Shivam Shukla
    Title : DP_D.cpp
    Date : 23/08/2020   >> 17:52:23


    Considering we are provided with the set of weights anbd having the values for each
    of them, now the point of the problem is to find the subset of this given set such that 
    the total sum of the weights in our consideration is at most W and the items cannot be
    used repeatedly i.e, the only magnitude in which each item of the given set is present is 1.

    Now the classic or brute force strategy of the problem will be to generate the subsets
    of the given set and whenever the set follows the condition that the total weight of the
    subset is less than or equal to W then we can update the value of ans and get the optimum / 
    maximum value we can attain doing this.

    Now the brute force solution gives us a very important hint, either each item can be 
    considered or will not be considered, therefore we have to deal with both of the cases.

    Consider we are examining each item for things to get done and easy. 

    We wil be going through each and every item to get the idea whether it will be considered 
    or not in our current subset or optimal answer.

    1. If the current item, 'i' is considered then, we would be solving the same problem for 
       (W - w[i]), but with the remaining set of items and not this item again. 

       That is we are solving the same problem for the (W - w[i]) but provided that we would 
       be considering the items that have been discovered 'j' where (j < i).

       Once we are trying to do this, the most important factor that comes into consideration
       is what happens when we are considering this item. 

       So provided that we have already considered this item, (W - w[i]) along with items smaller
       than i will be dealing with it.


    2. If the current item is not considered then as in the case 1, the items will be reduced
    to n - 1 while unlike the case 1, the weight that we can take is stil W. 

    In this case we just need to solve the problem (W - w[I]) but with j < i. 
    This is similar to the problem just being asked but with smaller constraints.

  So what is induced from these two cases ? 
        Optimal Substructure.


  Optimal Substructure is property by virtue of which the a bigger problem can be expressed,
  into the terms of the smaller possibilities.

  In this very case, the answer to our problem will be maximum of the answer that we get 
  from the case 1 and case 2.

  But still on the things have not resolved the time complexity is still the exponential,
  since we have just changed the perspective of the problem and not the code or algorithm. 

  Now provided this substructure lets try to solve the problem for N and W. 

  F(n, w) = max(F(n - 1, w - v[i]), F(n - 1, w))

  The recursion tree in itself will create multiple repetitions of the states, (n, w);
  exmaple suppose that it may contain (n - 3, w - 5) multiple times due to presence of multiple such
  weights or due to multiple configurations of weights which may lead to sum of 5. 

  Here the overlapping subproblem hallmark is pretty evident and therefore, it follows

  1. Optimal Substructure 
  2. Overlapping Subproblems

  Therefore its a DP problem with the states being :

  1. Amount of weight 
  2. Number of weights considered

  through which we have to optimize the value obtained through the weights.

  Now lets move to what are the trabnsition of DP states if we aim to go through a bottom up
  approach, here in this case following are the cases:

  1. If the present weight is considered : 
    i: weight, j : number of weights cponsidered

    if (i >= wt[j])
      dp[i][j] = dp[i - wt[j]][j - 1];

  2. If the present weight is not considered,
     
     // since we are not considering this weight at all so we are thinking to take 
     // answer from the previous item weightage (what is maximum we can obtain with those items)
     dp[i][j] = dp[i][j - 1]     

  Finally we can say that 

  dp[i][j] = dp[i][j - 1] 
  dp[i][j] = max(dp[i][j], (i >= wt[j]) ? dp[i - wt[j]][j - 1] : -INF(ll));

  Therefore, we can get the answer by the value of dp[w][n];
  
  This is very common classic DP problem known by names like, 

  0/1 Knapsack Problem - Bounded Knapsack Problem 
  in which we canot partition any of the items in the given item set.

*/

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pair<ll,ll> > vpll;
 
const int MOD=1e9+7;
const int MAX=1e5+5;
const double PI= acos(-1.0);
const long double EPS=1e-10;
const int64_t INF=1e18+10;
 
#define fastio() ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0)
#define trace(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vi vector<int>
#define vl vector<ll>
#define vs vector<str>
#define vc(x) vector<x>
#define mapll map<ll,ll>
#define mapib map<int,bool>
#define mapiv map<int,vector>
#define mapsi map<string,int>
#define rep(i,j,k) for(ll i=j;i<k;i++)
#define down(i,j,k) for(ll i=j;i>=k;i--)
#define repa(i,n) for(ll i=0;i<n;i++)
#define dowa(i,n) for(ll i=n;i>=0;i--)
#define reps(i,j,k,s) for(ll i=j;i<k;i+=s)
#define downs(i,j,k,s) for(ll i=j;i>=k;i-=s)
#define trv(i,x) for(auto i:x)
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define str string 
#define dub double
#define pqmax priority_queue<ll>
#define pqmin priority_queue<ll,vl,greater<ll> >
#define INF(x) numeric_limits<x>::max()
 
template<typename t> t lcm(t a, t b) {return (a*b)/__gcd(a,b);}
template<typename t> t gcd(t a, t b) {return __gcd(a,b);}
template<typename t> t mul_mod(t a, t b, t m){t res=((a%m)*(b%m)%m); return res;}
template<typename t> t add_mod(t a, t b, t m){t res=((a%m)+(b%m))%m; return res;}
template<typename t> t pow_mod(t a,t b,t m) {t res=1;while(b){if(b&1) res=mul_mod(res,a,m);a=mul_mod(a,a,m), b>>=1;} return res%m;}
template<typename t> vc(t) num_vec(t num) {t res; while (num) res.pb(num%10), num/=10; return res;}
template<typename t> t vec_num(t vec) {t res=0; ll mul=1; repa(i,sz(vec)) res=vec[i]*mul, mul*=10; return res;}
 

int32_t main(int argc,char** argv){
    fastio();
    auto tstart= clock();

    #ifndef ONLINE_JUDGE
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
      freopen("error.txt","w",stderr);
    #endif   

    int n, w; cin >> n >> w;
    vpll a(n); repa(i, n) cin >> a[i].ff >> a[i].ss;
 
    vc(vl) dp(w + 1, vl(n + 1, 0));
    rep(i, 1, w + 1) 
      rep(j, 1, n + 1) 
        dp[i][j] = max(dp[i][j - 1], (i >= a[j - 1].ff) ? a[j - 1].ss + dp[i - a[j - 1].ff][j - 1] : -INF(ll));
 
    cout << dp[w][n] << endl;

    cerr << setprecision(2) << fixed<<"Time elapsed: " << (double)(clock() - tstart)/CLOCKS_PER_SEC << endl; 
    return 0; 
}

Measured memory_bytes: 85328