#include<bits/stdc++.h>
#define ll                      long long 
#define vll                     vector<ll>
#define pb                      push_back
#define MOD                     1000000007
#define ld                      long double
#define vpll                    vector<pair<ll,ll>>
#define vll                     vector<ll>
#define pll                     pair<ll,ll>
#define pld                     pair<ll,ld>
#define all(x)                  x.begin(),x.end()
#define fi                      first
#define se                      second
#define ln                      cout<<"\n";
#define test                    ll T;cin>>T;while(T--)
#define fastIO                  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll gcd(ll a,ll b){if(a<b)return gcd(b,a);else if(b==0)return a;else return gcd(b,a%b);}
bool isprime(ll n){for(ll i=2;i*i<=n;i++)if(n%i==0)return 0;return 1;}
ll pow(ll b,ll e){if(e==0)return 1;else if(e%2==0){ll a=pow(b,e/2);return a*a;}else {ll a=pow(b,e/2);return b*a*a;}}
ll powm(ll x,ll y,ll m=MOD){x=x%m;ll res=1;while(y){if(y&1)res=res*x;res%=m;y=y>>1;x=x*x;x%=m;}return res;}
ll lcm(ll a,ll b){ return (a*b)/gcd(a,b);}
ll modInverse(ll a, ll m) { return powm(a, m-2, m);}
bool issq(ll n){ ll p=sqrt(n);return p*p==n;}
ll MIN(ll a=2e18,ll b=2e18,ll c=2e18,ll d=2e18,ll e=2e18){return min(a,min(b,min(c,min(d,e))));}
ll MAX(ll a=-2e18,ll b=-2e18,ll c=-2e18,ll d=-2e18,ll e=-2e18){return max(a,max(b,max(c,max(d,e))));}
vector<int> prime;// if i==prime[i] then prime otherwise smallest prime factor of that number
void seive(ll n){
prime.resize(n+5,0);ll j;for(ll i=2;i<=n;i++){if(!prime[i]){prime[i]=i;for(j=i*i;j<=n;j+=i)if(!prime[j])prime[j]=i;}}}
ll extended_GCD(ll a ,ll b ,ll &x ,ll &y){
    if(a == 0){
        x = 0;
        y = 1;
        return b;
    }
    ll x1 , y1;
    ll gcd = extended_GCD(b%a , a , x1 , y1);
    x = y1 - (b/a)*x1; 
    y = x1;
    return gcd;
}
ll mulInv(ll a , ll mod){
    ll x , y;
    extended_GCD(a , mod , x , y);
    if(x < 0) x += mod;
    return x;
}
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << "'" << x << "'";}
void __print(const char *x) {cout << '"' << x << '"';}
void __print(const string &x) {cout << '"' << x << '"';}
void __print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}

int main()
{

#ifdef ONLINE_JUDGE
	auto start_time = clock();
	#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
	freopen("input.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("out.txt", "w", stderr);
#else
	#define debug(x...)
	fastIO; 
#endif

ll n,w;
cin>>n>>w;
ll weight[n+1]={},value[n+1]={};
ll s=0;
for(ll i=1;i<=n;i++)
{
	cin>>weight[i]>>value[i];
	// s+=weight[i];
}
ll dp[n+1][w+1]={};
for(ll i=1;i<=n;i++)
{
	for(ll j=0;j<=w;j++)
	{
		if(j-weight[i]<0)
		{
			dp[i][j]=dp[i-1][j];
		}
		else
		{
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
		}
	}
}
cout<<dp[n][w];
#ifdef ONLINE_JUDGE
auto end_time = clock();
cout << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
return 0;
}

Measured memory_bytes: 79232