/// http://abc060.contest.atcoder.jp/tasks/arc073_b
 
 
/// Bismillahir Rahmanir Rahim
/// S. M. Shakir Ahsan Romeo ( Pure_Protea, #theromeo421, Cosmos_Freak )
/// CSE Discipline, Khulna University, Khulna
/// Monirampur, Jessore.
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long lng;
typedef vector < int >  vi;
typedef vector < lng >  vl;
typedef pair < int, int >  pii;
typedef vector < pii >  vpii;
 
const int inf = 1 << 30;
const long long linf = 1LL << 62;
const double PI = acos(-1.0), dinf = (double)(1LL << 62), eps = (double)(1e-9);
 
double distance(double x1, double y1, double x2, double y2)
{
    x1 -= x2;
    y1 -= y2;
    return sqrt(x1 * x1 + y1 * y1);
}
long long POW(long long b, long long p)
{
    if(p == 0)
        return 1;
    long long t = POW(b, p >> 1);
    if(p & 1)
        return t * t * b;
    return t * t;
}
long long bigmod(long long b, long long p, long long m)
{
    if(p == 0)
        return 1;
    long long t = POW(b, p >> 1) % m;
    t = (t * t) % m;
    if(p & 1)
        t = (t * b) % m;
    return t;
}
inline int getint()
{
    int x;
    scanf("%d", &x);
    return x;
}
inline long long getlng()
{
    long long x;
    scanf("%lld", &x);
    return x;
}
 
lng gcd(lng a, lng b)
{
    return !b ? a : gcd(b, a % b);
}
 
lng lcm(lng a, lng b)
{
    return (a / gcd(a, b)) * b;
}
 
int dx4[] = {-1, 0, 1, 0};
int dy4[] = {0, 1, 0, -1};
int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};
 
#define theromeo421 main()
#define segtree int lft = node << 1, rgt = lft | 1, mid = (b + e) >> 1;
#define mem(x, y) memset(x, y, sizeof x);
#define II getint()
#define LL getlng()
#define sz(x) ((int)x.size())
#define sqr(x) ((x) * (x))
#define max3(a,b,c) max(a, max(b,c))
#define min3(a,b,c) min(a, min(b,c))
#define pr1(x) cout << x << endl
#define pr2(x,y) cout << x << ' ' << y << endl
#define pr3(x,y,z) cout << x << ' ' << y << ' ' << z << endl
#define pr4(a,b,c,d) cout << a << ' ' << b << ' ' << c << ' ' << d << endl
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define repab(i, a, b) for(int i = a; i <= b; ++i)
#define repstl(it, x) for(auto it = x.begin(); it != x.end(); it++)
#define repbstl(it, x) for(auto it = x.rbegin(); it != x.rend(); it++)
#define forch(it, x) for(auto it : x)
#define pb push_back
#define all(x) x.begin(), x.end()
#define xx first
#define yy second
#define dbg(x) cerr << #x << " :  " << x << endl;
#define read(a) freopen(a, "r", stdin);
#define write(a) freopen(a, "w", stdout);
#define prv(v) rep(i, v.size()) cout << v[i] << " \n"[i + 1 == v.size()];
#define prmp(x) repstl(it, x) pr2(it->xx, it->yy)
#define pause int ppause; cin >> ppause;
#define pf printf
#define sf scanf
 
const int N = 101;
int n, W, arr[N], v[N];
map < lng , int > dp[N];
 
int call(int i, lng w)
{
    if(i == n)
        return 0;
    if(dp[i].find(w) != dp[i].end())
        return dp[i][w];
    int ret = call(i + 1, w);
    if(w + arr[i] <= W)
        ret = max(ret, v[i] + call(i + 1, w + arr[i]));
    return dp[i][w] = ret;
}
 
int theromeo421
{
    n = II;
    W = II;
    rep(i, n)
    {
        arr[i] = II;
        v[i] = II;
        dp[i].clear();
    }
    printf("%d\n", call(0, 0));
    return 0;
}

Measured memory_bytes: 6272