//Submitted by Anushree 
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(c) c.begin(), c.end()
#define inf 1000000000
#define ninf -1000000000
#define for0(i,n) for(int i=0;i<n;i++)
#define fori(i,a,n) for(int i=a;i<n;i++)
#define dfor(i,n,d) for(int i=n;i>=d;i--)
#define mem(ar,x) memset(ar,x,sizeof ar)
inline long long  max2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  max3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  min2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  min3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int,int> > vii;
typedef long long ll;
#define  modu 1000000007
#define pi 3.141592653589793238462643383279502884
int dr8[]={0,0,1,-1,1,1,-1,-1};
int dc8[]={1,-1,0,0,-1,1,-1,1};
int dr4[]={0,1,-1,0};
int dc4[]={1,0,0,-1};
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
inline void deb_vi(vi a) {fori(i, 0, a.size()) cout<<a[i]<<" ";}
inline void deb_vll(vll a) {fori(i, 0, a.size()) cout<<a[i]<<" ";}
inline bool is_palindrome(const string& s){ return std::equal(s.begin(), s.end(), s.rbegin()); }
using namespace std; 
#define N 10000000
 // int fib[N]={0};
// bool prime[N+1]; 
// void Sieve() 
// { 
//     // bool prime[n+1]; 
//     memset(prime, true, sizeof(prime)); 
//     prime[1]=false;
//     for (int p=2; p*p<=N; p++) 
//     { 
//         if (prime[p] == true) 
//         { 
//             for (int i=p*p; i<=N; i += p) 
//                 prime[i] = false; 
//         } 
//     } 
//     // int c = 0;
//     // for (int p=2; p<=N; p++) 
//     //    if (prime[p]) {
//     //        c++;
//     //       cout<<c<<" "<< p << " ";
//     //    }
// } 
// int spf[N];
// void primeFactors()
// {
// 	for(int i=0;i<=N;i++)
// 		spf[i]=i;
// 	for(int s=2;s*s<=N;s++)
// 	{
// 		if(spf[s]==s)
// 		{
// 			for(int i=s*s;i<=N;i=i+s)
// 			{
// 				spf[i]=s;
// 			}
// 		}
// 	}

// }

// ll power(ll a,ll b)
// {
//     a = a%modu;
//     ll result = 1;

//     while(b)
//     {
//         if(b&1)
//             result = (result*a)%modu;
//         b >>= 1, a = (a*a)%modu;
//     }
//     return result;
// }
ll gcd(ll a,ll b)
{
    if(a==0)
    return b;
    return gcd(a%b,a);
}
ll lcm(ll a,ll b)
{
    ll ans=(a*b)/gcd(a,b);
    return ans;
}
int main()
{
	fast

//   int T;
//     cin>>T;
//     while(T--){
         
         int n,W;
         cin>>n>>W;
         vi w(n),v(n);
         for(int i=0;i<n;i++)
         {
             cin>>w[i]>>v[i];
         }
      ll dp[n+1][W+1];
      
      for(int i=0;i<=W;i++)
      dp[0][i]=0;
      
      for(int i=0;i<=n;i++)
      dp[i][0]=0;
      
      for(int i=1;i<=n;i++)
      {
          for(int j=1;j<=W;j++)
          {
              if(w[i-1]>j)
              dp[i][j]=dp[i-1][j];
              
              else
              {
                  dp[i][j]=max(dp[i-1][j],v[i-1]+dp[i-1][j-w[i-1]]);
              }
          }
      }
      cout<<dp[n][W];
        // cout<< endl;
    // }
   return 0;
}






Measured memory_bytes: 79232