#include<bits/stdc++.h>
using namespace std;
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#pragma GCC optimize "trapv"
#define _GLIBCXX_DEBUG
#define ll long long int
#define ull unsigned long long int  // ranges from (0 - twice of long long int)
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define vll vector<ll>
#define mod 1000000007LL
#define llpair pair<ll,ll>
#define INF 1000000000000000000ll
#define np next_permutation
#define PI acos(-1)
#define deb(x) cout<<#x<<" "<<x<<endl;
#define rotate_left(vec,amt) rotate(vec.begin(),vec.begin()+amt,vec.end());
#define rotate_right(vec,amt) rotate(vec.begin(),vec.begin()+vec.size()-amt,vec.end());

//ALWAYS USE ll DATA TYPE FOR INTEGER(FASTER THAN INTEGER AS WELL AS SOMETIMES WITHOUT USE LONG UR ANSWER WILL NOT ACCEPTED) && DOUBLE FOR DECIMAL VALUE
template<typename T> // for removing front element from the vector
void pop_front(std::vector<T> &v)
{
    if (v.size() > 0) {
        v.erase(v.begin());
    }
}
template<typename R> // for removing back element from the vector or can directly
void pop_back(std::vector<R> &v) // use vec.pop_back() function...
{
    if (v.size() > 0) {
        v.erase(v.begin()+v.size()-1);
    }
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

ll less_than_or_equal_to(vector<ll>vec,ll k)   // Made by me // it is used to find the value which is either equal to or less than the given K value
{										       // if it returns -1 it means all the elements are greater than the required k element
	sort(vec.begin(),vec.end());
	if(vec[0]>k)
	return -1;
	else if(vec[vec.size()-1]<k)
	return vec[vec.size()-1];
	auto x=lower_bound(vec.begin(),vec.end(),k);
	if(k==*x)
	return *x;
	else
	{
		x--;
		return *x;
	}
}




bool isPerfectSquare(long double x)
{
  long double sr = sqrt(x);
  return ((sr - floor(sr)) == 0);
}

bool isprime(ll n)  //IN  O(sqrt(n))
{
    if(n<=1) return false;
    for(ll i=2;i*i<=n;i++)
        if(n%i==0)
            return false;

    return true;
}

void prime_factors(ll n)
{
	
	for(ll i=2;i*i<=n;i++)
	{
		
		if(n%i==0)
		{
			ll count=0;
			while(n%i==0)
			{
				count++;
				n=n/i;
			}
			
			cout<<i<<" "<<"^"<<" "<<count<<"\n";
		}
		
	}
	if(n>1)
	cout<<n<<" "<<"^"<<" "<<1<<"\n";
}


vector<ll> divisors(ll n){    //IN  O(sqrt(n))

    vll v;
    for(ll i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            v.pb(i);
            if((n/i)!=i)
            v.pb(n/i);
        }
    }
    return v;
}

ll power(ll a, ll n, ll m)  // using Binary Exponential in TC O(logn)
{                     // Self Written By </ME> :)
    ll res=1;
    while(n)
    {
        if(n%2) 
        res=(res*a)%m ,n--;
        else
        a=(a*a)%m ,n/=2;
    }
    return res;
}

ll ts(ll arr[],int l,int r,int x) // ternary search to find x in sorted array arr
{
    
    while(l<=r)
    {
        ll mid1= l+(r-l)/3;
        ll mid2= r -(r-l)/3;
        if(arr[mid1]==x || arr[mid2]==x)
            return 1;
        if(x<arr[mid1])
            r=mid1-1;
        else if(x>arr[mid2])
            l=mid2+1;
        else
        {
            l=mid1+1;
            r=mid2-1;
        }
    }

    return -1;
}


ll modulo_inverse(ll a, ll m)   // using little fermat theorem // Work in log(n) Time Complexity
{
	// Note:-> For calculating the modular inverse use power(a,m-2,m) as parameters values 
	// (condition is m should be prime and m & a must be coprime.)
	ll res=power(a,m-2,m); 
	return res;
}

ll crt(ll num[],ll rem[], ll n)   // chineser remainder theorem   // Time complexity is (nlogn)
{
	ll pp[n];
	ll p=1;
	for(int i=0;i<n;i++)
	p*=num[i];
	
	for(int i=0;i<n;i++)
	pp[i]=(p/num[i]);
	
	ll inv[n];
	for(int i=0;i<n;i++)
	inv[i]=modulo_inverse(pp[i],num[i]);
	
	ll ans=0;
	for(int i=0;i<n;i++)
	ans+=pp[i]*inv[i]*rem[i];
	
	return ans;
	
}


ll Extended_gcd(ll a, ll b, ll &x, ll &y)   // Simple Use is to find the coefficients of a,b if ax + by = gcd(a,b) is satisfying...:)
{
	if(b==0)
	{
		x=1;
		y=0; return a;
	}
	
	ll x1,y1;
	ll g = Extended_gcd(b,a%b,x1,y1);
	
	// value we get here
	x= y1;
	y= x1 - (a/b)*y1;
	
	return g;
}

/*
// ############# DISJOINT SET FUNCTIONS ##############

###################ABOUT FIND FUNCTION IN DISJOINT SET -> work always is to return the parent of the set nothing itn has to do
// In set you can't join one element to another element or linked any element to other element except
// the parent node, it means only parent Node Can Be Edditable In A SET
    
    
int find(ll n)
{
    if(parent[n]<0)
        return n;
    else
        return find(parent[n]); 
}

//############################### I LOVE UNION BY RANK ############## UMMMHHHHHHHH ###############
// If You are Only doing Union By Rank then there is no need to apply path compression baby
// If logic is simple that don't try to need the length of the tree make it as a logn by checking
// everytime the rank of element element during insertion

// ############### either do UNION BY RANK OR PATH COMPRESSION####################  
void uni(ll a,ll b)
{
    
    if(R[a]>R[b])
    {
        parent[a]+=parent[b];
        R[a]+=R[b];
        parent[b]=a;
    }
    else
    {
        parent[b]+=parent[a];
        R[b]+=R[a]; 
        parent[a]=b;
    }

    
}    
    
*/

/*   1.   Binary/Hexa/Octa to interger or decimal ->>>>>>  int d =stoi(s,nullptr,2); 

  
  	 2.	  Now Another is Decimal/Interger to Binary->>>>>  string k =bitset<32>(128).to_string();  
 */
 
 
ll count_freq(string &str ,string &substr)
{
	 //This code is used to count the frequency of particular substring in a given string using the found function
	ll count=0;
	size_t found = str.find(substr,0);
	while(found!=string::npos)
	{
		count++;
		found=str.find(substr,found+1);
		
	}
	
	return count;
	
}




int main() {
    auto start = chrono::high_resolution_clock::now();
    fio;
    ll t=1; 
    //cin>>t;
	while(t--)
	{
		ll n,w; cin>>n>>w;
		ll wt[n],val[n]; 
		{
			rep(i,0,n) 
			cin>>wt[i]>>val[i];
		}
		
		//for(auto x: val)
		//cout<<x<<" ";
		//cout<<"\n";
		
		ll dp[n+1][w+1]={0};
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=w;j++)
			{
				if(i==0 or j==0)
				dp[i][j]=0;
				else if(wt[i-1]>j)
				dp[i][j]=dp[i-1][j];
				else
				dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-wt[i-1]]);
			}
		}
		
		cout<<dp[n][w]<<"\n";
		
		
	}
	auto finish = chrono::high_resolution_clock::now();
    cerr << "Time elapsed: " << (chrono::duration<long double>(finish-start)).count() << "s\n";
    return 0;
        
	}



















Measured memory_bytes: 79232