#include <bits/stdc++.h>

using namespace std;

/***********************************************DEBUG_TEMPLATE***********************************************/                          
string to_string(string s) {
    return '"' + s + '"';
}

string to_string(const char* s) {
    return to_string((string) s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(char ch) {
    return string("'")+ch+string("'");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <class InputIterator>
string to_string (InputIterator first, InputIterator last) {
    bool start = true;
    string res = "{";
    while (first!=last) {
        if (!start) {
            res += ", ";
        }
        start = false;
        res += to_string(*first);
        ++first;
    }
    res += "}";
    return res;
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template<typename A,size_t N>
string to_string(A(&v)[N]){
    bool first = true;
    string res = "{";
    for (int i=0;i<N;i++) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template<size_t N>
string to_string(const bitset<N>& v)
{
    string res="";
    for (int i = 0; i < (int)v.size(); ++i) {
        res+= char('0'+v[i]);
    }
    return res;
}

string to_string(const vector<bool>& v)
{
    string res="";
    for (int i = 0; i < (int)v.size(); ++i) {
        res+= char('0'+v[i]);
    }
    return res;
}

void debug_out() {
    cerr << endl;
}

template <typename Head, typename... Tail>
void debug_out(Head&& H, Tail&&... T) {
    cerr << " " << to_string(forward<Head>(H));
    debug_out(forward<Tail>(T)...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 27
#endif
/**********************************************DEBUG_END****************************************************/

#define all(v) (v.begin(),v.end())
#define rall(v) (v.rbegin(),v.rend())
#define sz(v) (int)(v.size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ar array
#define lb lower_bound
#define ub upper_bound
#define forn(i, n) for(int i = 0; i < n ; ++i)
#define for1(i, n) for(int i = 1; i <=n ; ++i)
#define ford(i, n) for(int i = n-1; i>= 0;--i)
#define UNQ(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define mem(X,val) memset(X, val, sizeof((X)))
#define P(x) cout << x <<'\n';
#define W(x) cout << x;


typedef long long ll;
typedef double db;
typedef long double ld;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vector<int>>  vvi ;
typedef vector<vc> vvc;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpi ;

const db PI = acos(-1);
const ll mod = 1e9+7;
template <typename A, typename B>istream& operator>>(istream& input,pair<A,B>& x) {input>>x.F>>x.S;return input;}
template <typename A>istream& operator>>(istream& input,vector<A>& x) {for(auto& i:x)input>>i;return input;}
template<typename A>ostream& operator<<(ostream& output,vector<A>& x) {for(auto& i:x)output<<i<<' ';return output;}
template<class T> void _R(T &x) { cin >> x; } void R() {}template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...);}
template <class T>void smax(T& x,T y){ if(x<y)x=y;}
template <class T>void smin(T& x,T y){ if(x>y)x=y;}
template<typename T1, typename T2> T1 powz(T1 A, T2 B);
template <typename T1, typename T2>T1 ADD(T1,T2);
template <typename T1, typename T2>void ADDZ(T1&,T2);
template<class T1, class T2> T1 mul(T1 A, T2 B);
template<typename T1, typename T2> T1 GCD(T1 A,T2 B);
template<typename T1> T1 MOD(T1 A){return (A%mod + mod)%mod;}
/***************************************************main code**************************************************************/
const int MXN=1e6+5;
const ll INF = 9e18+200;
const int inf = 1e9+100;
const int mxn = 2e5+20;


void test_case()
{
	int n, W; cin >> n>> W;
	int w[n] , v[n];
	forn(i, n)
		cin >> w[i] >> v[i];
	vl dp(W+1,-inf);
	dp[0] = 0;
	forn(i, n){
		for(int j = W; j >= w[i]; --j)
			dp[j] = max(dp[j],dp[j-w[i]]+v[i]);		
    }
	debug(dp);
	ll ans = 0;
	for(ll i : dp)
		smax(ans,i);
	cout << ans;
}
/*************----------------------------******************/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef VIJY_DEFINE    
 freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
#endif
    int Tests = 1;
//    cin >> Tests;
    
    for(int tc = 1; tc <= Tests; ++tc){
        //cout <<"Case #"<<tc<<": ";
        test_case();
        cout<<'\n';
    }
#ifdef VIJY_DEFINE
    cerr << "Time elapsed: "<< 1.0*clock() / CLOCKS_PER_SEC <<"s.\n";
#endif   
}
template <typename T1, typename T2> 
T1 ADD(T1 A, T2 B)
{
    ll res = (A+B)%mod;
    if(res<0)res+=mod;
    return res;
}
template <typename T1, typename T2> 
void ADDZ(T1& A, T2 B)
{
    ll res = (A+B)%mod;
    if(res<0)res+=mod;
    A = res;
}
template<typename T1, typename T2>
T1 powz(T1 X,T2 B)
{
    ll A = X;
    ll res=1;
        A%=mod; 
        assert(B>=0); 
    for( ; B ; B>>=1){
        if(B&1)res=res*A%mod;
        A= A*A%mod;
    }
    return res;
}
template<typename T1, typename T2> 
T1 GCD(T1 A,T2 B)
{
     return B?GCD(B,A%B):A;
}
template <class T1 , class T2> 
T1 mul(T1 A, T2 B)
{
    ll res = 1;
    res = (1LL * A%mod * B%mod )%mod;
    return res;
}


Measured memory_bytes: 3884