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

#define FOR(i, l, r)  for (int(i) = int(l); int(i) <= int(r); ++i)
#define FORD(i, r, l) for (int(i) = int(r); int(i) >= int(l); --i)
#define hashmap unordered_map
#define hashset unordered_set
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#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 double          db;
typedef long long       ll;     typedef unsigned long long  ull;
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 vector<si>      vsi;
typedef set<ll>         sll;    typedef vector<sll>     vsll;
typedef set<pi>         spi;    typedef vector<spi>     vspi;
typedef set<pll>        spll;   typedef vector<spll>    vspll;
typedef vector<enum_t> ve;     typedef vector<ve>      vme;
typedef vector<string>  vs;     typedef vector<vs>      vms;
typedef vector<bool>    vb;     typedef vector<vb>      vmb;
typedef vector<char>    vc;     typedef vector<vc>      vmc;
typedef vector<int>     vi;     typedef vector<vi>      vmi;    
typedef vector<ll>      vll;    typedef vector<vll>     vmll;
typedef vector<pi>      vpi;    typedef vector<vpi>     vmpi;
typedef vector<pll>     vpll;   typedef vector<vpll>    vmpll;

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline void getInt(int& 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 void getLong(ll& 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 string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
char bufWrite[20];
template<typename T>inline void writeInt(T x)               {if(x<0)putchar('-'),x=-x;char*bufPos=bufWrite;do{*bufPos++=x%10+'0';}while(x/=10);do{putchar(*--bufPos);}while(bufPos>bufWrite);}
template<typename T>inline void printInt(T x, char c = EOF) {if(x<0)putchar('-'),x=-x;char*bufPos=bufWrite;do{*bufPos++=x%10+'0';}while(x/=10);do{putchar(*--bufPos);}while(bufPos>bufWrite);if(c!=EOF)putchar(c);}
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 tuple<T,T,T>extgcd(T a,T b){if(!a)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 <class T> T    bitGet    (T  x, int bit)           { return T(1) & (x >> (bit - 1)); }
template <class T> void bitSet    (T &x, int bit)           { x |=  (T(1) << (bit - 1)); }
template <class T> void bitReset  (T &x, int bit)           { x &= ~(T(1) << (bit - 1)); }
template <class T> void bitFlip   (T &x, int bit)           { x ^=  (T(1) << (bit - 1)); }
template <class T> void bitMake   (T &x, int bit, bool val) { x ^=  (T(1) << (bit - 1)) & (-val ^ x); }
/// ======================================================================
/// ======================================================================
// const db oo = 0.1 / 0; /// inf
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;


/// ======================================================================

int n, w;
vi wei, val;
ll trau()
{
    ll res = 0;
    for (int i = 0; i < (1 << n); ++i)
    {
        ll weight = 0, value = 0;
        for (int j = 0; j < n; ++j)
            if (i & (1 << j))
                if (weight + wei[j] <= w)
                    weight += wei[j],
                    value  += val[j];

        res = max(res, value);
    }
    return res;
}

vector<hashmap<int, ll> > f;
ll magic(int i = 0, int wgt = 0)
{
    if (i >= n) return 0;
    if (f[i].count(wgt)) return f[i][wgt];

    f[i][wgt] = magic(i + 1, wgt);
    if (wgt + wei[i] <= w)
        f[i][wgt] = max(f[i][wgt], magic(i + 1, wgt + wei[i]) + val[i]);
    
    return f[i][wgt];
}

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

    wei.resize(n);
    val.resize(n);

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

    if (n <= 20)
    {
        cout << trau();
        return 0;
    }

    if (1LL * n * w <= 1e5)
    {
        f.resize(n);
        cout << magic();
        return 0;
    }

    vll dp(w + 1, 0LL);
    for (int i = 0; i < n; ++i)
        for (int j = w; j >= wei[i]; --j)
            dp[j] = max(dp[j], dp[j - wei[i]] + val[i]);

    cout << dp.back();
    return 0;
}

Measured memory_bytes: 1024