/*
*@Author  Chand Vachhani
*/

#include<bits/stdc++.h>
#define int         long long
#define double      long double
#define vi          vector<int>
#define vii         vector<vector<int>>
#define pii         pair<int,int>
#define mii         map<int,int>
#define pb          push_back
#define pf          push_front
#define mp(a,b)          make_pair((a),(b))
#define vpii        vector<pair<int,int>>
#define fo(i,l,n)   for(int i{l}; i<n; i++)
#define rf(s)       for(auto &c : s)
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define PI          3.141592653589
#define sz(x)       (int)x.size()
#define bs(v,n)     binary_search(all((v)),(n))
#define lb(v,n)     lower_bound(all((v)),(n))
#define ub(v,n)     upper_bound(all((v)),(n))
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MOD         1000000007  


using namespace std;


template<class T>
T big(T a, T b) { return a>b ? a : b; }
int gcd(int a, int b) {  if (a == 0)  return b; return gcd(b % a, a); } 
int lcm(int a, int b) { return (a*b)/gcd(a,b); } 
bool mod(double a,double b) {return a/b - floor(a/b);}
int occurs(vi v,int n)  {  auto it=lb(v,n);auto it1=ub(v,n);int x=it1-it;return x;}
int logb(int base, int x) {return (log(x) / log(base));}
int pow(int n, int m){
    int ans=1;
    fo(i,0,m){
        ans*=n;
    }return ans;
}
int factors(int ans){
    int count=0;
    for (int i=1; i<=sqrt(ans); i++) { 
        if (ans%i == 0) 
        {if (ans/i == i) count++;
            else count+=2;} 
    }
    return count;     
}
bool isSubSequence(string str1, string str2, int m, int n)  // str1<str2
{ 
    // Base Cases 
    if (m == 0) return true; 
    if (n == 0) return false; 
  
    // If last characters of two strings are matching 
    if (str1[m-1] == str2[n-1]) 
        return isSubSequence(str1, str2, m-1, n-1); 
  
    // If last characters are not matching 
    return isSubSequence(str1, str2, m, n-1); 
} 

int fact(int n){
    if(n==0 || n==1) return 1;
    else return n*fact(n-1);
}

int f( int n, int dp[]){
    // if(n==0 || n==1 || n==2) return 1;
    // if(n==3) return 2;
    if(dp[n]!=0) return dp[n];
    int h1 = f(n-1,dp);
    int h2 = f(n-3,dp);
    int h3 = f(n-4,dp);    
    dp[n] = h1+h2+h3;
    return dp[n];    
}

int xnor(int a, int b) 
{ 
    // Make sure a is larger 
    if (a < b) 
        swap(a, b);  
  
    if (a == 0 && b == 0)  
        return 1;  
  
    int a_rem = 0; // for last bit of a 
    int b_rem = 0; // for last bit of b 
  
    // counter for count bit  
    // and set bit  in xnornum 
    int count = 0;  
  
    // to make new xnor number 
    int xnornum = 0; 
  
    // for set bits in new xnor number 
    while (a)  
    { 
        // get last bit of a 
        a_rem = a & 1;  
  
        // get last bit of b 
        b_rem = b & 1;  
  
        // Check if current two 
        // bits are same 
        if (a_rem == b_rem)         
            xnornum |= (1 << count); 
          
        // counter for count bit 
        count++;  
        a = a >> 1; 
        b = b >> 1;  
    } 
    return xnornum; 
} 

signed main(){
    tezz
  
    int n,p,k,q;
    cin >> n >> k;

    // mii mp;
    vi a,b;
    a.pb(0),b.pb(0);
    fo(i,0,n){
        cin >> p >> q;
        b.pb(p);
        a.pb(q);
    }
    
    // cout << a.size() << endl;
    int dp[a.size()+1][k+1]={0,0};

    fo(i,0,a.size()+1){
        fo(j,0,k+1){
            if(i==0 || j==0){
                dp[i][j]=0;
            }
            else if(b[i]<=j){                
                dp[i][j] = max( a[i]+dp[i-1][j-b[i]] , dp[i-1][j] );
                // cout << a[i] << " ";
            }
            else{
                dp[i][j] = dp[i-1][j];
                // cout << i << j << "*";
            }
            // cout << dp[i][j] << " ";
        }
        // cout << endl;
    }
    cout << dp[n][k];
    
    return 0;
}   


Measured memory_bytes: 80000