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


/*###   FAST-IO  ###*/


#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);


/*###   DEBUGGGGGGG   ###*/


#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define testcases int testcases;cin>>testcases; while(testcases--)
#define queries int queries;cin>>queries; while(queries--)

/*###   TO PRINT   ###*/

#define pp1(a) cout << a << endl;
#define pp2(a, b) cout << a << " " << b << endl;
#define pp3(a, b, c) cout << a << " " << b << " " << c << endl;
#define pp4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl;
#define pp5(a, b, c, d, e) cout << a << " " << b << " " << c << " " << d << " " << e << endl;

/*###   SSSSSSS   ###*/

#define INF INT_MAX

#define endl "\n"
#define ll long long
#define int long long

ll mod = 1e9+7;

#define pb push_back
#define mp make_pair

#define pii pair<int,int>
#define msi map<string,int>
#define vi vector<int>
#define vpii vector<pair<int,int>>


#define ff first
#define ss second
#define sz size()

#define REP(i,a,b) for(int i=a;i<=b;i++)
#define REP1(i,a,b) for(int i=a;i<b;i++)
#define f0(n) for(ll i=0;i<n;i++)
#define f(n) for(ll i=1;i<=n;i++)
#define fn(a,n) for(ll a=0; a<n; a++)
#define flr(a,l,r) for(ll a=l; a<=r;a++)

#define sorta(a) sort(a.begin(), a.end());
#define sortd(a) sort(a.begin(), a.end(), greater<ll>());
#define sortdp(a) sort(a.begin(), a.end(), greater<pair<ll, ll>>());

#define blb(a, b) lower_bound(all(a), b) - a.begin();
#define bub(a, b) upper_bound(all(a), b) - a.begin();


#define stop return 0


/*###   COMPARATOR   ###*/


bool rev(int x,int y)
{
    return x>y;
}


/*###   PAIR_SORT_IN_DESCENDING_ORDER  ###*/


bool sortinrev(const pair<int,int> &a,  
               const pair<int,int> &b) 
{ 
       return (a.first > b.first); 
}


/*###   MODULO   ###*/


int modulo(int x,int N){
    return (x % N + N) %N;
}


/*###   MAX & MIN   ###*/


int max(int a,int b)
{
    if(a>=b)
        return a;
    else     
        return b;
}

int min(int a,int b)
{
    if(a<=b)
        return a;
    else     
        return b;
}


/*###   MOD-DIFFERENCE   ###*/


ll diff(ll a,ll b)
{
    if(a>=b)
        return a-b;
    else
        return b-a;
}


/*###   PAIR-SORTING   ###*/


void pairsort(int a[], int b[], ll n)
{
    pair<int, int> pairt[n];
    for (int i = 0; i < n; i++) 
    {
        pairt[i].first = a[i];
        pairt[i].second = b[i];
    }

    sort(pairt, pairt + n);

    for (int i = 0; i < n; i++) 
    {
        a[i] = pairt[i].first;
        b[i] = pairt[i].second;
    }
}


/*###   GCD && LCM   ###*/


ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b); 
}

ll lcm (ll a, ll b) {
    return a / gcd(a, b) * b;
}


/*###   PRIME OR NOT   ###*/


int isPrime(int n)
{
    if(n < 2)
        return 0;
    if(n < 4)
        return 1;
    if(n % 2 == 0 or n % 3 == 0)
        return 0;
    for(int i = 5; i*i <= n; i += 6)
        if(n % i == 0 or n % (i+2) == 0)
            return 0;
    return 1;
}


/*###   nCr   ###*/


long long C(int n, int r) {
    if(r > n - r) r = n - r;
    long long ans = 1;
    int i;
    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}


/*###   MODULAR-EXPONENTIATION   ###*/


ll modexpo(ll x,ll p)
{
    ll res = 1;
    x = x%mod;
    while(p)
    {
        if(p%2)
            res = res * x;
        p >>= 1;
        x = x*x % mod;
        res %= mod;
    }
    return res;
}

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
  long double x;
  uint64_t c;
  int64_t r;
  if (a >= m) a %= m;
  if (b >= m) b %= m;
  x = a;
  c = x * b / m;
  r = (int64_t)(a * b - c * m) % (int64_t)m;
  return r < 0 ? r + m : r;
}



/*###   STRING TO INT   ###*/

int sti(string s) {
 
    int ans = 0;
    int p = 1;
 
    for (int i = s.size() - 1; i >= 0; i--) {
        ans = (ans + ((ll)(s[i] - '0') * p) % mod) % mod;
        p = (p * 10) % mod;
    }
    return ans;
 
}

/*###   TIMER   ###*/


void time() {
    #ifndef ONLINE_JUDGE
    cout << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    #endif
}

                                    /*************************** END OF TEMPLATE ****************************/


const int N=110000;

// int w[110],v[110];
// int dp[N];
//int dp[N][N];





int32_t main()
{
    

    IOS

    // int n,W;
    // cin>>n>>W;

    // for(int i=0;i<n;i++){
    // 	cin>>w[i]>>v[i];
    // }

    // for(int i=0;i<n;i++){
    // 	for(int j=W;j>=0;j--){
    // 		if(j+w[i]<=W){
    // 			dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i]);
    // 		}
    // 	}
    // }
    // int ans=0;
    // flr(i,0,W){
    // 	ans=max(dp[i],ans);
    // }
    // cout<<ans<<endl;

    //2nd Solution
    
    
    // int n,W;
    // cin>>n>>W;

    // vi w(110),v(110);
	

    // flr(i,0,n-1){
    // 	cin>>w[i]>>v[i];
    // }

    // for(int i=0;i<=n;i++){
    // 	for(int j=0;j<=W;j++){
    // 		if(i==0||j==0){
    // 			dp[i][j]=0;
    // 			continue;
    // 		}

    // 		if(j-w[i-1]>=0){
    // 			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
    			
    // 		}
    // 		else{
    // 			dp[i][j]=dp[i-1][j];
    // 		}
    // 	}
    // }

    // cout<<dp[n][W]<<endl;



    //3rd solution

    int N,W;
    cin>>N>>W;

    vi w(N),v(N);
    flr(i,0,N-1){
    	cin>>w[i]>>v[i];
    }

    vector< vector<ll> >dp(N+1,vector<ll>(W+1,0));

    for(int i=0;i<N;i++){
    	for(int j=0;j<=W;j++){
    		if(j-w[i]>=0){
    			dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i]);
    		}
    		
    			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
    		
    	}
    }

    cout<<dp[N][W]<<endl;
    






    
    //time();
    stop;
}

Measured memory_bytes: 80256