#include <bits/stdc++.h>
#define lli  long long int 
#define forr(i,a,n) for(i=a;i<n;i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define pi 3.1415926536
#define endl '\n'
#define mod 1000000007
#define mod1 998244353
#define mkp make_pair
#define N 100005
#define INF 1e18
#define double long double
#define query cin>>q;while(q--)

using namespace std;

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

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

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

lli binSearch(lli a[],lli l,lli h, lli x){
    lli c=-1;
    while(l<=h){
        lli m=(l+h)/2;
        if(a[m]>=x){
            c=m;
            h=m-1;
        }
        else l=m+1;
    }
    return c;
}

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

void rev_pairsort(lli a[], lli b[], lli n){
    pair<lli, lli> pairt[n];
    for (lli i = 0; i < n; i++) 
    {
        pairt[i].first = a[i];
        pairt[i].second = b[i];
    }
    sort(pairt, pairt + n);
    reverse(pairt, pairt + n);
    for (lli i = 0; i < n; i++) 
    {
        a[i] = pairt[i].first;
        b[i] = pairt[i].second;
    }
}

lli nod(lli n){
    lli c=0;
    while(n>0){
        c++;
        n/=10;
    }
    return c;
}

lli sod(lli n){
    lli s=0;
    while(n>0){
        s+=n%10;
        n/=10;
    }
    return s;
}

lli mulmod(lli a, lli b, lli mod2) 
{ 
    lli res = 0;
    a = a % mod2; 
    while (b > 0) 
    { 
        if (b % 2 == 1) 
            res = (res + a) % mod2; 
  
        a = (a * 2) % mod2; 
        b /= 2; 
    } 
  
    return res % mod; 
}

string intToString(lli n){
    string s ="";
    while(n>0){
        s+=char(n%10+'0');
        n/=10;
    }
    reverse(s.begin(), s.end());
    return s;
}

int myComp(pair<lli, lli> p1, pair<lli, lli>p2){
    if(p1.second < p2.second || (p1.second == p2.second && p1.first < p2.first))
        return 1;
    return 0;
}

lli getFractionModulo(lli a, lli b) 
{ 
    lli c = __gcd(a, b); 
  
    a = a / c; 
    b = b / c; 
  
    // (b ^ m-2) % m 
    lli d = modexpo(b, mod - 2); 
  
    // Final answer 
    lli ans = ((a % mod) * (d % mod)) % mod; 
  
    return ans; 
} 


int main(){
    IOS;
    lli n,p,q,r,m,k,i,j,f=0,g=0,h=1,sum=0,ans=0,l,x,y,total=0,d,minn=1e18,maxx=0,pos=0;
    lli W;

    cin>>n>>W;

    lli v[n], w[n], dp[n+1][W+1];

    forr(i,0,n){
        cin>>w[i]>>v[i];        
    }

    forr(i,0,n+1){
        forr(j,0,W+1){
            if(!i || !j)
                dp[i][j] = 0;
            else if(w[i-1] <= j)
                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];
    
    return 0;
}    


Measured memory_bytes: 79232