#pragma region template
#ifndef DEBUGGING
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC diagnostic ignored "-Wunused-result"
#endif

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define last(a) *(a).rbegin()
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;i++)
#define brep(i,a,b) for(int i=(a),i##_len=(b);i<=i##_len;i++)
#define rrep(i,n) for(int i=(n)-1,now=0;i>=0;i--,now++)
#define xrep(i,n) for(int i=1,i##_len=(n);i<=i##_len;i++)
#define yes(n) cout<<((n)?YES:NO)<<'\n'
#define co(n) cout<<n<<'\n'
#define fo(n) printf("%.15lf\n",(n))
#define fout cout<<fixed<<setprecision(15)
#define Sort(v) sort(all(v))
#define rSort(v) sort(all(v),greater<typeof(v[0])>())
#define Rev(v) reverse(all(v))
#define Unique(v) (v).erase(unique(all(v)),(v).end())
#define in_area(x,y,a,b) (0<=(x)&&0<=(y)&&(x)<(a)&&(y)<(b))
#define eb emplace_back
#define fi first
#define se second

#ifdef ONLINE_JUDGE
#define here()
#define cprint(vec)
#define comment(msg)
#define observe(...)
#define local(x)
#define alter(x,y) y
#else
#define here() cerr<<__func__<<'/'<<__LINE__<<": passed\n"
#define cprint(vec) printE(vec)
#define comment(msg) cerr<<"{ "<<msg<< " }\n"
#define observe(...) obs(#__VA_ARGS__, __VA_ARGS__)
#define local(x) x
#define alter(x,y) x
#endif

using namespace std;
using ll    = long long;
using ld    = long double;
using ull   = unsigned long long;
using vbl   = vector<bool>;
using dqbl  = deque<bool>;
using vint  = vector<int>;
using vll   = vector<long long>;
using vdbl  = vector<double>;
using vstr  = vector<string>;
using vvbl  = vector<vector<bool>>;
using vdqbl = vector<deque<bool>>;
using vvint = vector<vector<int>>;
using vvll  = vector<vector<long long>>;

template<class T>         using uset = unordered_set<T>;
template<class S,class T> using umap = unordered_map<S,T>;

constexpr int         INF   = 1e9;
constexpr long long   LINF  = 1e18;
constexpr double      EPS   = 1e-9;
constexpr long double LEPS  = 1e-18;

// --- functions which take 1 argument --- //
template<class T> inline int sgn(const T &x){return (x>0)-(x<0);}
template<class T> inline int digit(T x,const int &b=10){int r=1;while((x/=b)>=1)r++;return r;}
template<class T> inline double degToRad(const T &a){return a/180.0*M_PI;}
template<class T> inline double radToDeg(const T &a){return a/M_PI*180.0;}
template<class T> inline long long factorial(const T &n) {if(n==0)return 1;ll r=1;brep(i,2,n)r*=i;return r;}
template<class T> inline map<T,T> factorize(T n){map<T,T>r;for(T i=2;i*i<=n;i++){while(n%i==0){r[i]++;n/=i;}}if(n!=1)r[n]=1;return r;}
template<class T> inline vector<T> divisor(const T &n){vector<T>r;for(T i=1;i*i<=n;i++){if(!(n%i)){r.eb(i);if(i*i!=n)r.eb(n/i);}}return r;}

// --- functions which take more than 1 arguments --- //
template<class T> inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool in_range(const T &a,const T &b,const T &c){return b<=a&&a<c;}
template<class T> inline T    nPr(const T &n,const T &k){if(n<k||n<0||k<0)return 0;T r=1;brep(i,n-k+1,n)r*=i;return r;}
template<class T> inline T    nCr(const T &n,T k)       {if(n<k||n<0||k<0)return 0;T r=1;k=min(k,n-k);brep(i,n-k+1,n)r*=i;return r/factorial(k);}

// --- functions which take vector/deque as argument --- //
template<class T> inline void print(const vector<T> &v){cout<<"[ ";for(const auto &x:v)cout<<x<<' ';cout<<"]\n";}
template<class T> inline void print(const deque<T> &v) {cout<<"[ ";for(const auto &x:v)cout<<x<<' ';cout<<"]\n";}
template<class T> inline void print(const vector<vector<T>> &v){for(const auto &x:v)print<T>(x);}
template<class T> inline void print(const vector<deque<T>> &v) {for(const auto &x:v)print<T>(x);}
template<class T> inline void printD(const vector<T> &v,string d){rep(i,sz(v)-1)cout<<v[i]<<d;cout<<last(v)<<'\n';}
template<class T> inline void printD(const vector<vector<T>> &v,string d){for(const auto &x:v)printD(x,d);}
template<class T> inline bool in(const T &k,const vector<T> &v)         {return find(all(v),k)!=v.end();}
                  inline bool in(const int &k,const vector<ll> &v)      {return find(all(v),k)!=v.end();}
                  inline bool in(const ll &k,const vector<int> &v)      {return find(all(v),k)!=v.end();}
                  inline bool in(const char &k,const string &v)         {return find(all(v),k)!=v.end();}
                  inline bool in(const char* &k,const vector<string> &v){return find(all(v),k)!=v.end();}
template<class T> inline double abs(const vector<T> &v){return sqrt(reduce(all(v),0.0L,[](T s,T v){return s+=v*v;}));}
template<class T> inline T min(const vector<T> &v){return *min_element(all(v));}
template<class T> inline T max(const vector<T> &v){return *max_element(all(v));}
template<class T> inline T sum(const vector<T> &v){return reduce(all(v),(T)0);}
template<class T> inline T gcd(const vector<T> &v){T r=v[0];brep(i,1,sz(v)-1)r=gcd(r,v[i]);return r;}
template<class T> inline T lcm(const vector<T> &v){T r=v[0];brep(i,1,sz(v)-1)r=lcm(r,v[i]);return r;}
template<class T> inline T vectorAdd(const T &u,const T &v)     {T r(u.size());rep(i,u.size())r[i]=u[i]+v[i];return r;}
template<class T> inline T vectorSubtract(const T &u,const T &v){T r(u.size());rep(i,u.size())r[i]=u[i]-v[i];return r;}
template<class T> inline T vectorMultiply(const T &u,const T &v){T r(u.size());rep(i,u.size())r[i]=u[i]*v[i];return r;}
template<class T>         inline T                dotProduct(const deque<bool> &u,const vector<T> &v){T r=0;rep(i,u.size())if(u[i])r+=v[i];return r;}
template<class S,class T> inline common_type<S,T> dotProduct(const vector<S> &u,const vector<T> &v)  {T r=0;rep(i,u.size())r+=u[i]*v[i];return r;}
template<class S,class T> inline void sortBySecond(vector<pair<S,T>> &v){sort(all(v),[](auto L,auto R){return L.second<R.second;});}

// --- functions which take set/map as argument --- //
template<class T> inline T min(const set<T> &v) {return *min_element(all(v));}
template<class T> inline T min(const uset<T> &v){return *min_element(all(v));}
template<class T> inline T max(const set<T> &v) {return *max_element(all(v));}
template<class T> inline T max(const uset<T> &v){return *max_element(all(v));}
template<class T> inline T sum(const set<T> &v) {return reduce(all(v),(T)0);}
template<class T> inline T sum(const uset<T> &v){return reduce(all(v),(T)0);}
template<class T> inline T gcd(const set<T> &v) {T r=0;for(const T &x:v)r=(r==0)?x:gcd(r,x);return r;}
template<class T> inline T gcd(const uset<T> &v){T r=0;for(const T &x:v)r=(r==0)?x:gcd(r,x);return r;}
template<class T> inline T lcm(const set<T> &v) {T r=0;for(const T &x:v)r=(r==0)?x:lcm(r,x);return r;}
template<class T> inline T lcm(const uset<T> &v){T r=0;for(const T &x:v)r=(r==0)?x:lcm(r,x);return r;}
template<class T> inline bool in(const T &k,const set<T> &v) {return find(all(v),k)!=v.end();}
template<class T> inline bool in(const T &k,const uset<T> &v){return find(all(v),k)!=v.end();}
template<class T>         inline void print(const set<T> &v)   {cout<<"[ ";for(const T &x:v)cout<<x<<' ';cout<<"]\n";}
template<class T>         inline void print(const uset<T> &v)  {cout<<"[ ";for(const T &x:v)cout<<x<<' ';cout<<"]\n";}
template<class S,class T> inline void print(const map<S,T> &m) {cout<<"[ ";for(const auto &x:m)cout<<"{ "<<x.fi<<", "<<x.se<<" } ";cout<<"]\n";}
template<class S,class T> inline void print(const umap<S,T> &m){cout<<"[ ";for(const auto &x:m)cout<<"{ "<<x.fi<<", "<<x.se<<" } ";cout<<"]\n";}

// --- functions for debugging --- //
template<class T>            void obs(const char* n,T &&v)         {cerr<<n<<": "<<v<<'\n';}
template<class S,class... T> void obs(const char* n,S &&v,T&&... w){const char* c=strchr(n+1,',');cerr.write(n,c-n)<< ": "<<v<<" |";obs(c+1,w...);}
template<class T> inline void printE(const vector<T> &v)        {cerr<<"[ ";for(const auto &x:v)cerr<<x<<' ';cerr<<"]\n";}
template<class T> inline void printE(const vector<vector<T>> &v){for(const auto &x:v)printE<T>(x);}
#pragma endregion template

void solve(ll N, ll W, vector<ll> w, vector<ll> v) {
  vvll dp(N+1, vll(1.1e5, 0));
  xrep(i, N) {
    rep(weight, 1.1e5) {
      dp[i][weight] = dp[i-1][weight];
      if (weight >= w[i-1]) {
        chmax(dp[i][weight], dp[i-1][weight - w[i-1]] + v[i-1]);
      }
    }
  }
  co(dp[N][W]);
}

int main() {
  ll N;
  scanf("%lld",&N);
  ll W;
  scanf("%lld",&W);
  vector<ll> w(N);
  vector<ll> v(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&w[i]);
    scanf("%lld",&v[i]);
  }
  solve(N, W, move(w), move(v));
  return 0;
}


Measured memory_bytes: 90844