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


#define endl            '\n'
#define ll              long long
#define ld              long double 
#define ull             unsigned long long int
#define MOD             (ll)(1e9 + 7)
#define vi              vector<int>
#define vl              vector<long>
#define vll             vector<ll>
#define vs              vector<string>
#define pll             pair<ll,ll>
#define mll             map<ll,ll>
#define len(x)          x.length()
#define all(x)          x.begin(),x.end()
#define deb1(x)         cout<<#x<<" "<<x<<endl;
#define deb2(x,y)       cout<<#x<<" "<<x<<'    '<<#y<<" "<<y<<endl;
#define deb3(x,y,z)     cout<<#x<<" "<<x<<'    '<<#y<<" "<<y<<'    '<<#z<<" "<<z<<endl;
#define debug1(x)       cerr<<#x<<" "<<x<<endl;
#define debug2(x,y)     cerr<<#x<<" "<<x<<'    '<<#y<<" "<<y<<endl;
#define debug3(x,y,z)   cerr<<#x<<" "<<x<<'    '<<#y<<" "<<y<<'    '<<#z<<" "<<z<<endl;
#define info(s)         cerr<<s<<" "<<endl;
#define fr(a,b,c)       for(auto a=b;b<c?a<c:a>c;b<c?a++:a--)
#define frc(a,b,c)      for(auto a=b;a!=c;a++)
#define tr(it, a)       for(auto it = a.begin(); it != a.end(); it++)
#define lb(v,x)         lower_bound(v.begin(), v.end(), x)
#define ub(v,x)         upper_bound(v.begin(), v.end(), x)
#define clr(x)          memset(x, 0, sizeof(x))
#define GR              (double)(1 + sqrt(5)) / 2
#define fib(n)          (ll)round(pow(GR,n) / sqrt(5))
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define out1(x)         cout<<x<<" "<<endl
#define out2(x,y)       cout<<x<<" "<<y<<endl
#define SORT(a)         sort(all(a));
#define SORTR(a)        sort(all(a),greater<ll>());
#define ARRAY(a,n)      vll a; fr(i,0,n) { ll temp; cin>>temp; a.pb(temp); }  
#define PRINT(a)        for(auto x:a)cout<<x<<" ";cout<<endl
#define MAX             100050
#define pb              push_back
#define mp              make_pair
#define F               first
#define S               second



template<typename T>
void output_vector(const vector<T> , bool ,bool ,int ,int );


template<typename T>
ostream& operator<<(ostream &out,const vector<T> &v);


template<typename T>
istream& operator>>(istream &in,vector<T> &v);


//
ll dp[100][100006];


int t[2005][2005];


int knapsack(vi &wt,vi &val,int w,int n)
{
    // if(w==0||n==0)
    //     return 0;
    
    for(int i=0;i<n+1;i++){
        for(int j=0;j<w+1;j++){
            if(i==0||j==0)
                t[i][j]=0;
        }
    }
    
    
    for(int i=1;i<n+1;i++){
        for(int j=1;j<w+1;j++){
            if(wt[i-1]<=j)
            {
                t[i][j]=max(val[i-1]+t[i-1][j-wt[i-1]],t[i-1][j]);
            }
            else{
                t[i][j]=t[i-1][j];
            }
        }
    }
    
    return t[n][w];
    
    // if(t[n][w]!=-1)
    //     return t[n][w];
    // if(w>wt[n-1])
    //     return t[n][w]=max(val[n-1]+knapsack(wt,val,w-wt[n-1],n-1),knapsack(wt,val,w,n-1));
    // else
    //     return t[n][w]=knapsack(wt,val,w,n-1);
}


void solve(ll test)
{   
    memset(t,-1,sizeof(t));
    int w,n;cin>>n>>w;
    vi val(n),wt(n);
    for(int i=0;i<n;i++)
        cin>>wt[i]>>val[i];
    // cout<<knapsack(wt,val,w,n)<<endl;
    // return ;


    // dp[index][total W]

    dp[0][0]=0;
    dp[0][wt[0]]=val[0];

    for(int i=1;i<n;i++){
        dp[i][0]=0;
        for(int j=1;j<=w;j++){
            
            dp[i][j]=dp[i-1][j];

            if(j>=wt[i])
            dp[i][j]=max(dp[i][j],val[i]+dp[i-1][j-wt[i]]);
        }
    }

    ll ans =-1e18;

    for(int i=0;i<=w;i++){
        ans=max(ans,dp[n-1][i]);
    }

    cout<<ans<<endl;

} 


int main()
{   
    FIO;
    ll test;test=1;
    // cin>>test;
    for(ll i=1;i<=test;i++)
    solve(i);
    return 0;
}





template<typename T>
void output_vector(const vector<T> &v, bool debug_print=false,bool add_one = false,int start = -1, int end = -1) {
    if (start < 0) start = 0;
    if (end < 0) end = int(v.size());
 
    for (int i = start; i < end; i++)
        (debug_print)?(cerr << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n')):(cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n'));
}   


template<typename T>
ostream& operator<<(ostream &out,const vector<T> &v){
    int i=0;
    for(T x:v){
        out<<x;
        (i++!=v.size())?out<<' ':out<<'\n';    
    }
    return out;
}


template<typename T>
istream& operator>>(istream &in,vector<T> &v){
    for(T &i:v)
        in>>i;
    return in;
}

Measured memory_bytes: 96672