#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
// #include <bitset>
// #include <queue>
// #include <deque>
// #include <stack>
// #include <ctime>
// #include <iomanip>
// #include <cstdlib>
using namespace std;

/// ================================ Define Part ================================
#define minimize(a, b) a = min(a, b)
#define maximize(a, b) a = max(a, b)
#define FOR(i, l, r)  for (int(i) = int(l); int(i) <= int(r); i += 1)
#define FORD(i, r, l) for (int(i) = int(r); int(i) >= int(l); i -= 1)
#define hashmap unordered_map
#define hashset unordered_set
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eol '\n'
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define itr iterator
#define rtr reverse_iterator

enum enum_t {White, Black, Gray};
typedef unsigned long long ull;    typedef long long       ll;
typedef unsigned int    uint;      typedef double          db;
typedef pair<int, int>  pi;        typedef pair<ll, ll>    pll;
typedef map<int, int>   mi;        typedef map<ll, ll>     mll;
typedef set<int>        si;        typedef set<ll>         sll;       typedef vector<si>      vsi;       typedef vector<sll>     vsll;
typedef set<pi>         spi;       typedef set<pll>        spll;      typedef vector<spi>     vspi;      typedef vector<spll>    vspll;     
typedef vector<enum_t>  ve;        typedef vector<ve>      v2_e;      typedef vector<v2_e>    v3_e;      typedef vector<v3_e>     v4_e;
typedef vector<string>  vs;        typedef vector<vs>      v2_s;      typedef vector<v2_s>    v3_s;      typedef vector<v3_s>     v4_s;
typedef vector<bool>    vb;        typedef vector<vb>      v2_b;      typedef vector<v2_b>    v3_b;      typedef vector<v3_b>     v4_b;
typedef vector<char>    vc;        typedef vector<vc>      v2_c;      typedef vector<v2_c>    v3_c;      typedef vector<v3_c>     v4_c;
typedef vector<int>     vi;        typedef vector<vi>      v2_i;      typedef vector<v2_i>    v3_i;      typedef vector<v3_i>     v4_i;
typedef vector<ll>      vll;       typedef vector<vll>     v2_ll;     typedef vector<v2_ll>   v3_ll;     typedef vector<v3_ll>    v4_ll;
typedef vector<pi>      vpi;       typedef vector<vpi>     v2_pi;     typedef vector<v2_pi>   v3_pi;     typedef vector<v3_pi>    v4_pi;
typedef vector<pll>     vpll;      typedef vector<vpll>    v2_pll;    typedef vector<v2_pll>  v3_pll;    typedef vector<v3_pll>   v4_pll;

/// ================================ Independent  Functions ================================
template<typename T>inline tuple<T,T,T> extgcd(T a,T b) { if(a==0)return mt(b,0,1);T g,x,y;tie(g,x,y)=extgcd(b%a,a);return mt(g,y-(b/a)*x,x); }
template<typename T>inline         T       gcd(T a,T b) { while (b != 0) swap(b, a %= b); return a; }
template<typename T>inline         T       lcm(T a,T b) { return a / gcd(a, b) * b; }
template<typename T>inline bool bitGet   (T  x, int bit)         { return T(1) & (x >> bit); }
template<typename T>inline void bitSet   (T &x, int bit)         { x |=  (T(1) << bit); }
template<typename T>inline void bitReset (T &x, int bit)         { x &= ~(T(1) << bit); }
template<typename T>inline void bitFlip  (T &x, int bit)         { x ^=  (T(1) << bit); }
template<typename T>inline void bitMake  (T &x, int bit, bool v) { x ^=  (T(1) << bit) & (-v ^ x); }
template<typename T>inline void writeUnsign(T n) { if (n > 9) writeUnsign(n / 10);  putchar(n % 10 + '0'); }
template<typename T>inline void writeSigned(T x) { if (x < 0) putchar('-'), x = -x; writeUnsign(x);        }
template<typename T>inline void getString (T& s) {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');s.clear();s.pb(c);while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s.pb(c);}
template<typename T>inline void getUnsign (T& n) {char c;while(c=getchar(),c<'0'||c>'9');n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';}
template<typename T>inline void getSigned (T& n) {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign(c=='-');if(sign)c=getchar();n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';if(sign)n=-n;}
inline int    readInt()    { int x;    return getSigned(x), x; }    inline uint readUINT()   { uint x; return getUnsign(x), x; }
inline ll     readLong()   { ll  x;    return getSigned(x), x; }    inline ull  readULL()    { ull  x; return getUnsign(x), x; }
inline string readString() { string s; return getString(s), s; }    inline vc   readVecStr() { vc   s; return getString(s), s; } 
inline void file_inp(const string FILE = "Test") { freopen((FILE + ".INP").c_str(), "r", stdin);  }
inline void file_out(const string FILE = "Test") { freopen((FILE + ".OUT").c_str(), "w", stdout); }
inline void file    (const string FILE = "Test") { file_inp(FILE); file_out(FILE); }
/// ================================ Dependent  Functions ================================
// const db oo = 0.1 / 0; /// inf
// const db PI = acos(-1);
const ll LINF = (1LL << 60); /// 1e18
const int INF = (1 << 30); /// 1e9
const int LIM = (1 << 24); /// 1e7
const int MOD = 1e9 + 7;
const int BASE = 1e4;
const int DIGIT = 4;
const int MAXVAL = 1e6 + 500;

/// ================================ Main part ================================

int query()
{


    return 0;
}

int main()
{
    // file(); 

    int n = readInt();
    int w = readInt();

    vi wei(n), val(n);
    for (int i = 0; i < n; ++i)
    {
        getUnsign(wei[i]);
        getUnsign(val[i]);
    }

    if (n <= 20) {
        ll res = 0; 
        for (int mask = 0, lim = 1 << n; mask < lim; ++mask) {
            ll weight = 0, value = 0;
            for (int i = 0; i < n; ++i)
                if (bitGet(mask, i))
                    if (weight + wei[i] <= w)
                        weight += wei[i],
                        value  += val[i];
        
            maximize(res, value);
        }

        cout << res;
        return 0;
    }

    vll dp(w + 1, 0);
    for (int i = 0; i < n; ++i)
        for (int j = w; j >= wei[i]; --j)
            maximize(dp[j], dp[j - wei[i]] + val[i]);
	
    cout << dp.back();
    return 0;
}

Measured memory_bytes: 3552