#include<bits/stdc++.h>
using namespace std;
#define ll long long int
typedef unsigned long long int ull;
typedef long double ldb;
#define B 1000000007
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repi(i,a,b) for(ll i=b-1;i>=a;i--)
#define MT make_tuple
#define G(a,b) get<a>(b)
#define VI vector<int>
#define VLL vector<long long int>
#define pb push_back
#define mp make_pair
#define INF 1e18
#define deci(n) fixed << setprecision(n)
#define PI 3.141592653589793238462643
#define ani ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

void pairsort(ll a[], ll b[], ll n) 
{ 
    pair<ll, ll> pairt[n]; 
  
 
    for (ll i = 0; i < n; i++)  
    { 
        pairt[i].first = a[i]; 
        pairt[i].second = b[i]; 
    } 
  
    sort(pairt, pairt + n); 
      
    for (ll i = 0; i < n; i++)  
    { 
        a[i] = pairt[i].first; 
        b[i] = pairt[i].second; 
    } 
}
 
ll extendedGcd(ll a, ll b, ll & x, ll & y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    ll x1, y1;
    ll d = extendedGcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}


  ll binaryToDecimal(string n) 
{ 
    string num = n; 
    ll dec_value = 0; 
    // Initializing base value to 1, i.e 2^0 
    ll base = 1;  
    ll len = num.length(); 
    for (ll i = len - 1; i >= 0; i--) { 
        if (num[i] == '1') 
            dec_value += base; 
        base = base * 2; 
    } 
    return dec_value; 
} 


ll nCr(ll n,ll k){ 
    ll C[n + 1][k + 1]; 
    ll i, j; 
    for (i=0;i<=n;i++){ 
        for(j=0;j<=min(i,k);j++){
            if(j==0||j==i) 
                C[i][j]=1;  
            else
                C[i][j]=(C[i-1][j-1]%B+C[i-1][j]%B)%B; 
        } 
    }
    return C[n][k]%B; 
} 


ll countDivisors(ll n) 
{ 
    ll cnt = 0; 
    for (ll i = 1; i <= sqrt(n); i++) 
    { 
        if (n % i == 0) 
        { 
            // If divisors are equal, 
            // count only one 
            if (n / i == i) 
                cnt++; 
  
            else // Otherwise count both 
                cnt = cnt + 2; 
        } 
    } 
    return cnt; 
}

ll highestPowerof2(ll n) 
{ 
   ll p = (ll)log2(n); 
    return (ll)pow(2, p);  
} 
bool isPowerOfTwo(int x)
    {   // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
        return (x && !(x & (x - 1)));
    }

void dfs(int p,vector<int> a[],int v[])
{
    if(v[p])
        return ;
    v[p]=1;
    for(int i=0;i<a[p].size();i++)
    {
        if(!v[a[p][i]])
        dfs(a[p][i],a,v);
    }
} 
ll max(ll a, ll b){
  if (a > b)
    return a;
  return b;
}
ll min(ll a, ll b){
  if (a < b)
    return a;
  return b;
}

int main()
{ 
ani;

int t=1;
 // cin>>t;
while(t--)
{

    ll n;
    cin>>n;
    ll W;
    cin>>W;
    ll w[n];
    ll v[n];
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];

    ll k[n+1][W+1];

     for(int i=0;i<=n;i++)
        for(int j=0;j<=W;j++)
        {
            if(i==0 || j==0)
                k[i][j]=0;
            else if(j>=w[i-1])
                k[i][j]=max(v[i-1]+k[i-1][j-w[i-1]],k[i-1][j]);
            else
                k[i][j]=k[i-1][j];
        }
cout<<k[n][W];












}

return 0;
}

Measured memory_bytes: 79232