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

#define ff first
#define ss second
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define mp make_pair
#define endl "\n"      // Comment in INTERACTIVE(there just use endl which flushes output , no need of fflush(sdtout)).
//  for counting setbits -> __builtin_popcountll(x)
// for counting zerobits -> __builtin_ctzll(x)
#define fastio() ios_base::sync_with_stdio(false);        cin.tie(NULL); //(unties i/o buffer).
            // DON'T USE SCANF/PRINTF WITH IT (c/c++ -> seperates buffer).

const int mod = 1000000007;
const int inf = 1000000009;
 const int N = (1e5) + 2;
 int w[102] ;
 int v[102];
 int dp[100 + 2][N];
 int memo[100 + 2][N];

 int cnt;
 int cnt1;
// Recursive
int knapsack(int left,int i,int n){
    if(i > n)
        return 0;
    int ans = knapsack(left,i+1,n);
    if(left >= w[i])
        ans = max(ans,knapsack(left - w[i], i+1,n) + v[i]);
    cnt1++;
    return ans;
    // Here have 2 attributes that decide state -> i and left.
    // Hence in memo , store state using them.
}

// *** In solution , POSSIBILITY THAT ONLY SOME STATES USED.
/* Have ARGUMENTS , with some values HAVE STATES POSSIBLE (based on ARGUMENT RANGE).
    Hence in BOTTOM-UP , ALL STATES ARE FILLED.

    Whereas IN MEMOIZATION ONLY THOSE STATES/SUBSTATES FILLED which are needed.
    HENCE ****MANY TIMES MAY BE FASTER THAN BOTTOM-UP.
*/

/*
Given input
6 15
6 5
5 6
6 4
6 6
3 5
7 2

Output -> * OUT of 90 POSSIBLE STATES , ONLY 27 USED

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 17 
-1 -1 -1 -1 -1 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 17 
-1 -1 -1 -1 5 -1 -1 -1 -1 11 11 -1 -1 -1 -1 15 
-1 -1 -1 5 5 -1 -1 -1 -1 11 11 -1 -1 -1 -1 11 
-1 -1 -1 5 5 -1 -1 -1 -1 5 7 -1 -1 -1 -1 7 
0 0 -1 0 0 -1 0 2 -1 2 2 -1 2 -1 -1 2 

** Because WEIGHTS >= 3 , ALL LARGE VALUES , many >= 6 , so SUBSTATES USED SAME (others not used).
    Hence only some states utilised.
*/



int knapmemo(int left,int i,int n){
    if(i > n)
        return 0;
    if(memo[i][left] != -1)
        return memo[i][left];

    int ans = knapmemo(left,i+1,n);
    if(left >= w[i]){
        ans = max(ans,knapmemo(left - w[i], i+1,  n) + v[i]);
    }
    
    cnt++;

    return memo[i][left] = ans;
}

int bottomup(int n,int net){

    for(int i = n;i > 0 ;--i){
        for(int j = net; j > 0; --j){
            dp[i][j] = dp[i+1][j];
            if(j >= w[i]){
                dp[i][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
            }
        }
    }
    return dp[1][net];
}

int32_t main(){
    fastio();

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

     // ***** AC_chahiye EK BAR MEIN

     // BEGIN CODE HERE
     memset(memo,-1,sizeof(memo));  // set memo as -1.
    int n , net;
    cin>>n>>net;


    for(int i = 1;i <= n; ++i){
        cin>>w[i]>>v[i];
    }
    
    // cout<<knapsack(net, 1,n)<<"     "<<knapmemo(net, 1,n)<<endl;
    // cout<<cnt<<endl;
    // for(int i = 1;i <= n; ++i){
    //     for(int j = 0;j <= net; ++j){
    //         cout<<memo[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    cout<<bottomup(n,net)<<endl;
    //getch();
}


Measured memory_bytes: 158848