/*****************/
/*

Sharma Ji Ka Ladka
MNNIT Allahabad

*/
/*****************/

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

#define For(i,a,b)                              for (int i=a;i<b;i++)
#define Forl(i,size)                            for (int i=0;i<size;i++)
#define Forr(i,size)                            for (int i=size-1;i>=0;i--)
#define ForR(i,a,b)                             for(int i=a;i>=b;i--)
#define s(n)                                    scanf("%d",&n)
#define p(n)                                    printf("%d\n",n)
#define ps(n)                                   printf("%s\n",n)
#define sd(n)                                   int n;scanf("%d",&n)
#define sl(n)                                   long long int n;scanf("%lld",&n)
#define pb(n)                                   push_back(n)
#define clr(a)                                  memset(a,0,sizeof(a))
#define all(c)                                  (c).begin(),(c).end()
#define len                                     length()
#define size                                     size()
#define mp(a,b)                                 make_pair(a,b)
#define fi first
#define se second
typedef unsigned long long ull;
#define ret return 0;
#define PI 3.14159265
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);   
const long long Mod =1e9+7; 
// string a,b,s,c,d;

typedef vector <int> vi;
typedef vector <vi> vvi;
typedef vector <string> vst;
typedef vector <bool> vb;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
ll sum=0,ans=0,res=0;
int i, j, k;



bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ if(a.se==b.se)
    return (a.fi < b.fi);

    return (a.se < b.se); 
}

// IS PRIME FUNCTION STARTS   

bool isPrime(ll num){
    bool flag=true;
    if(num==1)return false;
    for(int i = 2; i <= sqrt(num); i++) {
       if(num % i == 0) {
          flag = false;
          break;
       }
    }
    return flag;
}

//IS PRIME FUNCTION ENDS


//**Array Sum Function**

ll findSum(ll a[],int l,int r)
{ll sum=0;
    For(i,l,r)
    {
        sum+=a[i];
    }
    return sum;
}

//**Array Sum Function Ends**


//Prime Factors Of A Number 

vector<pair<int,int>> vec1; //Prime Factors along with their exponents
void primeFactors(ll n) 
{ int c1=0;
	// Print the number of 2s that divide n 
	while (n%2 == 0) 
	{ 
		// printf("%d ", 2); 
		n = n/2;c1++; 
	} if(c1)
    vec1.pb(mp(2,c1));
c1=0;
	// n must be odd at this point. So we can skip 
	// one element (Note i = i +2) 
	for (int i = 3; i <= sqrt(n); i = i+2) 
	{ c1=0;
		// While i divides n, print i and divide n 
		while (n%i == 0) 
		{ 
			// printf("%d ", i); 
		    
            n = n/i;c1++; 
		} 
        if(c1)
        vec1.pb(mp(i,c1));
	} 
c1=0;
	// This condition is to handle the case when n 
	// is a prime number greater than 2 
	if (n > 2) 
	vec1.pb(mp(n,1));
} 

//Ends



//*** Power Function Starts
ll power(int x, unsigned int y) 
{ 
    int temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2); 
    if (y%2 == 0) 
        return temp*temp; 
    else
        return x*temp*temp; 
} 
//*** Power function ends 

//nCr function starts

ull nCr(ll n,ll r)
{
ull p=1;ull k=1;
if(n-r<r)
r=n-r;

if(r!=0)
{
    while(r)
    {
        p*=n;k*=r;
        ll m=__gcd(p,k);
        p/=m;k/=m;     //Simplifying 
        n--;r--;
    }

}
else p=1;

return p;


}


//nCr function ends


// ** LCM of two numbers
ll lcm(ll a, ll b){
    return a / __gcd(a, b) * b;
}
//** Ends //


//** Count Set Bits Functon

unsigned int countBits(ll n,int specify) 
{ 
    unsigned int count = 0,total=0; 
    if (n==0){if(specify == 1)return 0;else return 1;}
    while (n) { 
        total+=1;
        count += n & 1; 
        n >>= 1; 
    } 
    if(specify==1)
    return count; 
    else return (total-count);
}

//** Ends //


//Array Scanner starts

void scar(ll a[],int n)
{
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
}

//Array Scanner ends
//  long long findTargetSumWays(vector<int>& vec, int S) {
        
//         long long sum=0;
//         for(int i=0;i<vec.size;i++)
//         {
//             sum+=vec[i];
//         }
//         // cout<<sum<<endl;
//         if(sum<S||(sum+S)%2!=0)return 0;
//         long long s1=(sum+S)/2;
        
//         long long dp[vec.size+10][s1+10]={0};
//         for(int j=0;j<s1+1;j++)
//         {
//             dp[0][j]=0;
//         }
//         for(int i=0;i<vec.size+1;i++)
//         {
//             dp[i][0]=1;
//         }
//         for(i=1;i<vec.size+1;i++)
//         {
//             For(j,0,s1+1)
//             {if(j>=vec[i-1])
//                 dp[i][j]=dp[i-1][j]+dp[i-1][j-vec[i-1]];
//                 else
//                 {
//                     dp[i][j]=dp[i-1][j];
//                 }
                
//             }
//         }
//         return dp[vec.size][s1];
      
//     }



signed main() {
    // boost
string aux1,aux2,aux3;

    int T = 1;
    // cin>>T;
    Forl(ZA,T)
    {int f=0,fl1=0,fl2=0,c1=0,c2=0,cont=0,cnt=0,c3=0,auxi=0,auxj=0;
    ll mi=INT_MAX;ll ma=INT_MIN,sol=0;

    int n;
    cin>>n;
    ll w;cin>>w;
    pair<ll,ll> knap[n];
    For(i,0,n)
    {
        cin>>knap[i].fi>>knap[i].se;
    }
    ll dp[n+1][w+1];
    memset(dp,0,sizeof dp);
    for(int i=1;i<n+1;i++)
    {
        for(int j=1;j<w+1;j++)
        {
           if(j>=knap[i-1].fi)
           {
              dp[i][j]=max(dp[i-1][j],knap[i-1].se+dp[i-1][j-knap[i-1].fi]);
           }
           else
           {
               dp[i][j]=dp[i-1][j];
           }
           
        }
    }
cout<<dp[n][w]<<endl;

    }
    return 0;
}



Measured memory_bytes: 79104