/********************************************************************************************/
/************************************** BAAZIGAR ********************************************/
/********************************************************************************************/
 
                                                                                            //
#include <bits/stdc++.h>                                                                    //       
using namespace std;                                                                        //
                                                                                            //
typedef long long ll;                                                                       //
typedef long double ld;                                                                     //
typedef unsigned long long ull;                                                             //
typedef vector<ll> vec;                                                                     //
#define inf LONG_LONG_MAX                                                                   //
#define minf LONG_LONG_MIN                                                                  //
#define pq priority_queue                                                                   //
#define pi 3.1415926535897932                                                               //
                                                                                            //   
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);                     //
#define rall(container) container.rbegin(), container.rend()                                //
#define all(container)  container.begin(), container.end()                                  //
#define bp              __builtin_popcountll                                                //
#define f(i,l,r)        for(ll i=l;i<r;i++)                                                 //
#define rf(i,r,l)       for(ll i=r;i>=l;i--)                                                //
#define ull             unsigned long long                                                  //
#define yuss            cout << "YES\n";                                                    //
#define nope            cout << "NO\n";                                                     //
#define nl              endl                                                                //
#define ff              first                                                               //
#define ss              second                                                              //
#define sz              size()                                                              //
#define mp              make_pair                                                           //
#define pb              push_back                                                           //
#define pll             pair<ll, ll>                                                        //
#define pii             pair<int, int>                                                      //
#define d1(a)           cout<<a<<endl;                                                      //
#define d2(a,b)         cout<<a<<' '<<b<<endl;                                              //
#define d3(a,b,c)       cout<<a<<' '<<b<<' '<<c<<endl;                                      //
#define d4(a,b,c,d)     cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;                              //
#define d5(a,b,c,d,e)   cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<endl;                      //
                                                                                            // 
#include <ext/pb_ds/assoc_container.hpp>                                                    //
#include <ext/pb_ds/tree_policy.hpp>                                                        //
using namespace __gnu_pbds;                                                                 //
#define o_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> //
                                                                                     
const ll mod = 1e9 + 7;                                                               
const int mx = 1e5 + 69; 
const ll INF = 1e18;
 
bool prime(ll x) {
    if (x < 2) return false;
    for (ll i = 2; i*i <= x; ++i) {
        if (x%i == 0) return false;
    }
    return true;
}
ll powerm(ll a,ll b,ll m=mod) {
	a%=m;
	ll res=1%m;
	while(b>0)
	{
		if(b & 1)
		    res=(res*a)%m;
		b>>=1;
		a=(a*a)%m;
	}
	return res;
}
ll power(ll a,ll b) {
	ll res=1;
	while(b>0)
	{
		if(b & 1)
		    res=(res*a);
		b>>=1;
		a=(a*a);
	}
	return res;
}
ll mul(ll x, ll y) {
   return (x * 1ll * y);
}
long double ncr(ll n, ll r){
    if (n==1 || r==0) return 1;
    if (r > n/2) r = n-r;
    long double ans = 1;
    for (ll i=1 ; i<=r ; i++) {
        ans *= ((long double)n / i);
        n--;
    }return ans;
}
ll invm(ll a) { return powerm(a,mod-(ll)2); }
ll mulm(ll x,ll y) { return ((x%mod)*(y%mod)) % mod; }
ll summ(ll x,ll y) { return (x%mod+ y%mod) % mod; }
ll subm(ll x,ll y) { return ((x%mod)-(y%mod)+mod) % mod;}
ll divm(ll x,ll y) { return mulm(x,invm(y));}

static bool mycmp(int &num1, int &num2)
{
	return (num1 > num2);
}
 
int solve() {
 	ll n, W;
	 
	cin >> n >> W;
	
	vector <ll> w(n+1), v(n+1);
	
	vector <vector<ll> > dp(n+1, vector<ll> (W+1, 0ll));
	
	for (int i=1 ; i<=n ; i++) cin >> w[i] >> v[i];
	
	for (int i=1 ; i<=n ; i++)
	{
		for (int j=1 ; j<=W ; j++)
		{
			dp[i][j] = dp[i-1][j];
			
			if (j-w[i] >= 0) 
			{
				dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);	
			}	
		}	
	}
	
	d1(dp[n][W])		
	
    return 0;
}
 
signed main() {
   FAST
   int q = 1;
   //cin >> q;
   while (q--)
   solve();
}  

Measured memory_bytes: 83096