#include<bits/stdc++.h>
#include <queue> 
#include<map>
#define ll long long
#define ull unsigned long long 
#define ld long double
#define all(ar) ar.begin(), ar.end()
#define sot(bello) bello.begin(),bello.end()
#define bitc  __builtin_popcountl
#define mp make_pair
#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (int i = n - 1; i >= 0; i--)
#define fill(ar,val) memset(ar, val, sizeof(ar))
#define fill0(ar) fill((ar), 0)
#define MAXN   100010 
#define MOD 1000000007
#define debug(x) cout<<#x<<": "<<x<<endl
#define dbug(x) cout<<#x<<": "<<x<<" "
#define fi first
#define se second
#define arr1d(a,n) cout << #a << " : "; fr(_,1,n) cout << a[_] << ' '; cout << endl;
#define arr1d0(a,n) cout << #a << " : "; rep(_,n) cout << a[_] << ' '; cout << endl;
#define arr2d(a,n,m) cout << #a << " :" << endl; fr(_,1,n) {fr(__,1,m) cout << a[_][__] << ' '; cout << endl;}
#define arr2d0(a,n,m) cout << #a << " :" << endl; rep(_,n) {rep(__,m) cout << a[_][__] << ' '; cout << endl;}

# define INF 1000000000000000
const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};



using namespace std;
//gcd
ll Gcd(ll a,ll b){
	if(a%b==0) return b;
	return Gcd(b,a%b);
}
//max
ll Max(ll a,ll b){
	if(a>b)
	return a;
	return b;
}
//min
ll Min(ll a,ll b){
	if(a<b)
	return a;
	return b;
}


void printvector(std::vector<ll> v){  for (int i = 0; i < v.size(); ++i){cout<<v[i]<<" ";}cout<<""<<endl;}
void printarray(ll a[],ll n){for (ll i = 0; i < n; ++i){cout<<a[i]<<" ";}cout<<""<<endl;}

ll findlcm(vector<ll> arr, ll n) 
{ 
    // Initialize result 
    ll ans = arr[0]; 
  
    // ans contains LCM of arr[0], ..arr[i] 
    // after i'th iteration, 
    for (int i = 1; i < n; i++) 
        ans = (((arr[i] * ans)) / 
                (Gcd(arr[i], ans))); 
  
    return ans; 
} 


ll gcdExtended(ll a, ll b, ll *x, ll *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }
 
    ll x1, y1; 
    ll gcd = gcdExtended(b%a, a, &x1, &y1);
 
    *x = y1 - (b/a) * x1;
    *y = x1;
 
    return gcd;
}




   
 
 ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;      
    x = x % p;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
  
        y = y>>1; 
        x = (x*x) % p;   
    } 
    return res; 
} 






ll modInverse(ll a, ll m)
{
    ll x, y;
    ll g = gcdExtended(a, m, &x, &y);
    if (g != 1)
        return -1 ;
    else
    {
        
        ll res = (x%m + m) % m;
        return res;
    }
}





vector<ll> primeFactors(ll n)
{    
    vector<ll> v;
	while (n%2 == 0)
	{
		v.push_back(2);
		n = n/2;
	}
	for (int i = 3; i <= sqrt(n); i = i+2)
	{
		while (n%i == 0)
		{
			v.push_back(i);
			n = n/i;
		}
	}

	if (n > 2)
		v.push_back(n);
		return v;
}


ll lowerbound(ll k,vector<ll> v){
  ll l=0;
  ll size=v.size();
  ll r=size-1;
  ll mid;
  while (l<=r)
  {
      mid=(l+r)/2;
      if(v[mid]<k) l=mid+1;
      else{
          r=mid-1;
      }
  }
  return l;

}

ll upperbound(ll k,vector<ll> v){
  ll l=0;
  ll size=v.size();
  ll r=size-1;
  ll mid;
  while (l<=r)
  {
      mid=(l+r)/2;
      if(v[mid]>k) r=mid-1;
      else{
          l=mid+1;
      }
  }
  return l;

}


ll C[2001][2000]; 

void binomialCoeff(ll n, ll k) 
{ 
   
    ll i, j; 
  
    // Caculate value of Binomial Coefficient in bottom up manner 
    for (i = 0; i <= n; i++) 
    { 
        for (j = 0; j <= k; j++) 
        { 
            // Base Cases 
            if (j == 0 || j == i) 
                C[i][j] = 1; 
  
            // Calculate value using previosly stored values 
            else
                C[i][j] = (C[i-1][j-1]%MOD + C[i-1][j]%MOD)%MOD; 
        } 
    } 
  
    //return C[n][k]; 
} 







  
ll spf[MAXN]; 
  
void sieve() 
{ 
    spf[1] = 1; 
    for (int i=2; i<MAXN; i++) 
      spf[i] = i; 
   for (int i=4; i<MAXN; i+=2) 
        spf[i] = 2; 
  
    for (int i=3; i*i<MAXN; i++) 
    { 
        if (spf[i] == i) 
        { 
           for (int j=i*i; j<MAXN; j+=i) 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
} 




ll binarySearch(ll arr[], ll l, ll r, ll x)
{
   if (r >= l)
   {
        ll mid = l + (r - l)/2;
        if (arr[mid] == x)  
            return mid;
 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid-1, x);
 
        return binarySearch(arr, mid+1, r, x);
   }
 
   return -1;
}


//Segment Tree Implementation

          const ll N = 100000; 
 
ll n; 
 
           ll tree[2 * N];

void build( ll arr[]) 
{ 
    for (ll i=0; i<n; i++)    
        { tree[n+i] = arr[i];
	       
	     }
     
    for (ll i = n - 1; i > 0; --i)     
        {tree[i] = tree[i<<1] + tree[i<<1 | 1];    
              /* cout<<"i<<1  is "<<(i<<1)<<endl;
               cout<<"i<<1 | 1  is "<<(i<<1 | 1)<<endl;*/
	     }
}
 
void updateTreeNode(ll p, ll value) 
{ 
    tree[p+n] = value;
    p = p+n;
     
    for (ll i=p; i > 1; i >>= 1)
        {tree[i>>1] = tree[i] + tree[i^1];
	       }
}
 
ll query(ll l, ll r) 
{ 
    ll res = 0;
     
    for (l += n, r += n; l < r; l >>= 1, r >>= 1)
    {
        if (l&1) 
           {    
			   res += tree[l++];
               
               }    
        if (r&1) 
             {   res += tree[--r];
				 
            }
    }
     
    return res;
}


//Dijkstra's Algorithm

vector<ll> shortPath( vector<pair<ll,ll> > v[],ll src,ll V=0) 
{ 
     set< pair<ll,ll> > setds; 
  
    ll sizee=V;
    ll IN=0x3f3f3f3f;
    vector<ll> dist(sizee, IN); 
  
    setds.insert(make_pair(0, src)); 
    dist[src] = 0; 
  
    while (!setds.empty()) 
    { 
        pair<ll, ll> tmp = *(setds.begin()); 
        setds.erase(setds.begin()); 
  
        ll u = tmp.second; 
  
        vector< pair<ll, ll> >::iterator i; 
        for (i = v[u].begin(); i != v[u].end(); ++i) 
        { 
            ll v = (*i).first; 
            ll weight = (*i).second; 
      if (dist[v] > dist[u] + weight) 
            { 
                if (dist[v] != INF) 
                    setds.erase(setds.find(make_pair(dist[v], v))); 
  
                dist[v] = dist[u] + weight; 
                setds.insert(make_pair(dist[v], v)); 
            } 
        } 
    }
    return dist;
} 


struct DSU
{
	ll connected, left[N], right[N];
	ll par[N], sz[N];

	void init(ll n) 
	{
		for(ll i=1;i<=n;i++)
		{
			par[i]=i;
			sz[i]=1;
			left[i]=i;
			right[i]=i;
		}
		connected=n;
	}

	ll getPar(ll k)
	{
		while(k!=par[k])
		{
			par[k]=par[par[k]];
			k=par[k];
		}
		return k;
	}

	ll getSize(ll k)
	{
		return sz[getPar(k)];
	}

	void unite(ll u, ll v)
	{
		ll par1=getPar(u), par2=getPar(v);

		if(par1==par2)
			return;

		connected--;

		if(sz[par1]>sz[par2])
			swap(par1, par2);

		sz[par2]+=sz[par1];
		sz[par1]=0;
		par[par1]=par[par2];
	}
};


ll dsu[100005];
ll fpar(ll i) 
{
	return (dsu[i]<0)?i:dsu[i]=fpar(dsu[i]);
}
void merge(ll i, ll j) 
{
	if((i=fpar(i))!=(j=fpar(j))) 
	{
		if(dsu[i]>dsu[j])
			swap(i,j);
		dsu[i]+=dsu[j];
		dsu[j]=i;
	}
}


// Sieve Implementation
/* 
for (ll i=2;i<=100005;i++)
        if (p[i]==0)
        for (ll j=2*i;j<=100005;j+=i) p[j]=1; */


// Dfs search

void dfs(std::vector<ll> v[],ll s,bool visited[])
{
	visited[s]=true;
  for (ll i = 0; i < v[s].size(); ++i)
  {
  	if(!visited[v[s][i]] )
  	{ 
  		dfs(v,v[s][i],visited);

  	}

  }


}





//do not use n , N , C


// Using iterators in C++ 
//set<ll>:: iterator it;

    





int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
ll w;
cin>>w;
ll dp[n+1][w+1];
ll we[n];
ll v[n];
rep(i,n){
    cin>>we[i];
    cin>>v[i];

}
rep(i,n+1){
    dp[i][0]=0;
}
rep(i,w+1){
    dp[0][i]=0;
}
fr(i,1,n){
    fr(j,1,w){
        ll mx=-1;
        if(j>=we[i-1]){
            mx=max(mx,dp[i-1][j-we[i-1]]+v[i-1]);
            mx=max(mx,dp[i-1][j]);
        }
        else
        {
            mx=max(mx,dp[i-1][j]);
        }
        dp[i][j]=mx;
        
    }
}
cout<<dp[n][w]<<endl;

 //return 0;
}









Measured memory_bytes: 81152