/*

   #
  # #    #    #   ####   #    #  #    #
 #   #   ##   #  #       #    #  #    #
#     #  # #  #   ####   ######  #    #
#######  #  # #       #  #    #  #    #
#     #  #   ##  #    #  #    #  #    #
#     #  #    #   ####   #    #   ####

*/
  #include<bits/stdc++.h>
  #include <ext/pb_ds/assoc_container.hpp> 
  #include <ext/pb_ds/tree_policy.hpp> 
  #define int long long int 
  #define hell 1000000007 
  #define F first
  #define re 15000000
  #define S second
  #define pb push_back
  #define all(a)  (a).begin(),(a).end()
  #define rep(i,a,b) for(int i = a;i<b;i++)
  #define pi 3.1415926536
  #define Mod 998244353
  #define endl '\n'
  #define TIME  cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
  #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> 
  using namespace std;
  using namespace __gnu_pbds; 

    int binarySearch(int x,int y ,int z ,int v[])
    {
        int low = x;
        int high = y;
        int mid = x+(y-x)/2;
        while(low<=high)
        {
            if(v[mid]==z)
                return mid;
            if(v[mid]<z)
                return binarySearch(mid+1,high,z,v);
            if(v[mid]>z)
                return binarySearch(low,mid-1,z,v);
        }
        return -1;
    }
  int modularExponentiation(int x, int y, int m) 
  { 
      if (y == 0) 
          return 1; 
      int p = modularExponentiation(x, y/2, m) % m; 
      p = (p * p) % m; 
    
      return (y%2 == 0)? p : (x * p) % m; 
  } 
    int binaryExponentiation(int x,int n)
    {
        if(n==0)
            return 1;
        else if(n%2 == 0)        //n is even
            return binaryExponentiation(x*x,n/2);
        else                             //n is odd
            return x*binaryExponentiation(x*x,(n-1)/2);
    }
   
   
   
   
    set<string> s;
    //vector<int> v;
    void genrate(string n,int len,int max)
    {
        if(n.size() == max){
          s.insert(n);
          return ;
        }
        genrate(n+'1',len+1,max);
        genrate(n+'0',len+1,max);
    }
    // bool visited[200005];
    // vector<int> v[200005];
    // bool recur[200005];
    // int c = 0;
    // void dfs(int x ,int parent)
    // {
    //    visited[x] = 1;
    //    if(v[x].size() != 2)
    //     c = -1;
    //    for(int i = 0;i<v[x].size();i++){
    //     if(v[x][i] == parent)
    //       continue;
    //     if(visited[v[x][i]] && v[x].size() == 2 && c ==  0)
    //         c = 1;
    //     else if(!visited[v[x][i]]){
    //      dfs(v[x][i],x);
    //    }
    //    //return false;
    //     }
    // }
    //memset(level,0,sizeof(level));    
    //char a2001][2001];
    ///**************** Cycle using DSU *********************///
  /* int topological_sort(int x)
  {
     vis[x] = 1;
     sort(all(v[x]));
     ans.pb(x);
     last[x] = x;
      for(int i =0;i<v[x].size();i++)
      {
          if(vis[v[x][i]]!=1){
              last[x] = topological_sort(v[x][i]);
          }
      }
      return last[x];
  }
*/ 
  int my_lower(vector<int> &v, int X){
    int lo = 0, hi = v.size()-1;
    if(v.size() == 0)
      return -1;
    while(hi-lo > 1){
      int mi = (lo+hi)/2;
      if(v[mi] < X){
        lo = mi;
      }
      else  
        hi = mi-1;
    }
    int ans = -1;
    for(int i = lo;i<=hi;i++){
      if(v[i] < X){
        ans = i;
      }
    }
    if(ans != -1 && v[ans] < X){
      return ans;
    }
    else
      return -1;
  }
  int my_upper(vector<int> & v, int X){
    if(v.size() == 0)
      return -1;
     int lo = 0, hi = v.size()-1;
    while(hi-lo > 1){
      int mi = (lo+hi)/2;
      if(v[mi] < X){
        lo = mi+1;
      }
      else
        hi = mi;
    }
    int ans = -1;
    for(int i = hi;i>=lo;i--){
      if(v[i] > X){
        ans = i;
      }
    }
    if(ans != -1 && v[ans] > X){
      return ans;
    }
    else
      return -1;
}
void Print(int t, int c){
  cout<<"Case #"<<t<<": "<<c<<endl;
}
int dp[101][100002];
int32_t main()
{   
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cout.tie(0);            
    std::setprecision(20);        
    int tests=1;  
    //freopen("input.txt", "r", stdin);
    // cin>>tests;
    // int tc = 0;
    // vector<int>    
    while(tests--)   
    {
      int n,w;
      cin>>n>>w;
      vector<pair<int,int> >v(n+1);
      for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        v[i] = {x,y};
      }
      memset(dp, 0, sizeof(dp));
      for(int j = 0;j<=w; j++){
        if(j < v[1].F)
           dp[1][j] = 0;
        else
          dp[1][j] = v[1].S;
      }
      for(int i=2;i<=n;i++){
        for(int j = 0;j<=w;j++){
          if(j-v[i].F >= 0){
            dp[i][j] = max(dp[i][j], max(dp[i-1][j-v[i].F] + v[i].S, dp[i-1][j]));
          }
          else
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
      }
      cout<<dp[n][w];

    }
}

Measured memory_bytes: 82488