/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

using namespace std;

template<class T> using V = vector<T>;
template<class S, class T> using P = pair<S, T>;

using ll = long long;
using ull = unsigned long long;
using vl = V<ll>;
using vvl = V<vl>;
using vvvl = V<vvl>;
using pl = P<ll, ll>;
using vpl = V<pl>;
using vvpl = V<vpl>;
using vs = V<string>;
using ql = queue<ll>;
using qpl = queue<pl>;
using mapl = map<ll, ll>;
using setl = set<ll>;
using pql = priority_queue<ll>;

#define int ll

#define FOR(i, a, b) for(ll i=(a);i<=(ll)(b);i++)
#define RFOR(i, a, b) for(ll i=(b);i>=(ll)(a);i--)
#define REP(i, a) FOR((i),0,(ll)(a)-1)
#define REP0(i, a) FOR((i),0,(ll)(a))
#define REP1(i, a) FOR((i),1,(ll)(a))
#define RREP(i, a) RFOR((i),0,(ll)(a)-1)
#define RREP0(i, a) RFOR((i),0,(ll)(a))
#define RREP1(i, a) RFOR((i),1,(ll)(a))

#define ALL(obj) (obj).begin(),(obj).end()

#define SORT(a) sort((a).begin(),(a).end())
#define RSORT(a) sort((a).rbegin(),(a).rend())
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define BINS(a, b) binary_search((a).begin(),(a).end(),(b))
#define LOWB(a, b) (lower_bound((a).begin(),(a).end(),(b))-(a).begin())
#define UPB(a, b) (upper_bound((a).begin(),(a).end(),(b))-(a).begin())
#define REV(a) reverse((a).begin(),(a).end())

#define COUNT(a, b) count((a).begin(),(a).end(),b)
#define SUM(a) accumulate((a).begin(),(a).end(),0)

#define IOTA(a, n) iota((a).begin(),(a).end(),(n))

#define yes(a) cout <<((a)?"yes":"no")<<endl
#define Yes(a) cout <<((a)?"Yes":"No")<<endl
#define YES(a) cout <<((a)?"YES":"NO")<<endl
#define possible(a) cout <<((a)?"possible":"impossible")<<endl
#define Possible(a) cout <<((a)?"Possible":"Impossible")<<endl
#define POSSIBLE(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl

#define DEBUG(a) cerr <<(#a)<<": "<<(a)<<endl
#define DIGN2(a) ((llabs(a)==0)?(1):((ll)(log2(double(llabs(a))))+1))
#define DIGN10(a) ((llabs(a)==0)?(1):((ll)(log10(double(llabs(a))))+1))
#define DIG2(a, b) (((a)>>(b))&1)
#define DIG10(a, b) (ll)(((a)/((ll)(pow(10.0,(double)(b)))))%10)

#define POW2(a) ((ll)(1)<<(a))
#define POW10(a) ((ll)(pow(10.0,double(a))))
#define POWl(a, b) (ll)(pow((double)(a),(double)(b)))

#define CIN(...) ll __VA_ARGS__;Input(cin,__VA_ARGS__)
#define CINS(...) string __VA_ARGS__;Input(cin,__VA_ARGS__)
#define CINV(size, ...) vl __VA_ARGS__;vInput(cin,size,__VA_ARGS__)
#define CINVS(size, ...) vs __VA_ARGS__;vInput(cin,size,__VA_ARGS__)

#define COUT(...) Output(cout,__VA_ARGS__)
#define COUTV(x) for(auto&youso_: (x) )cout<<youso_<<" ";cout<<endl
#define COUTSP(...) OutputSP(cout,__VA_ARGS__)

const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = 924844033;
//const ll MOD = 9007199254740881;
const ll INF = 1LL << 60;//1.15e18
const double PI = acos(-1.0);
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void Input() {}

template<class... Args>
void Input(istream &cin, Args &... args) {}

template<class Var, class... Args>
void Input(istream &cin, Var &var, Args &... args) {
    cin >> var;
    Input(cin, args...);
}

void Output() {}

template<class... Args>
void Output(ostream &cout, Args ... args) { cout << endl; }

template<class Var, class... Args>
void Output(ostream &cout, Var var, Args ... args) {
    cout << var;
    Output(cout, args...);
}

void OutputSP() {}

template<class... Args>
void OutputSP(ostream &cout, Args &... args) {}

template<class Var, class... Args>
void OutputSP(ostream &cout, Var &var, Args &... args) {
    cout << var << " ";
    Output(cout, args...);
}

void vInit(istream &cin, ll size) {}

template<class T, class... Args>
void vInit(istream &cin, ll size, V<T> &v, Args &... args) {
    v.resize(size);
    vInit(cin, size, args...);
}

void vInputNum(istream &cin, ll num) {}

template<class T, class... Args>
void vInputNum(istream &cin, ll num, V<T> &v, Args &... args) {
    cin >> v[num];
    vInputNum(cin, num, args...);
}

void vInput(istream &cin, ll size) {}

template<class... Args>
void vInput(istream &cin, ll size, Args &... args) {
    vInit(cin, size, args...);
    REP(i, size) vInputNum(cin, i, args...);
}

template<class S, class T>
ostream &operator<<(ostream &out, const P<S, T> &p) {
    return out << "[" << p.first << ", " << p.second << "]";
}

template<class T>
ostream &operator<<(ostream &out, V<T> &v) {
    if (v.empty()) return out << "{}";
    else {
        auto itr = v.begin();
        out << "{" << *itr;
        itr++;
        while (itr != v.end()) {
            out << ", " << *itr;
            itr++;
        }
        out << "}";
        return out;
    }
}

template<class S, class T>
ostream &operator<<(ostream &out, const map<S, T> &m) {
    if (m.empty()) return out << "<[]>";
    else {
        auto itr = m.begin();
        out << "< [" << (itr->first) << ": " << (itr->second);
        itr++;
        while (itr != m.end()) {
            out << "], [" << (itr->first) << ": " << (itr->second);
            itr++;
        }
        out << "] >";
        return out;
    }
}

template<class T>
ostream &operator<<(ostream &out, const set<T> &s) {
    if (s.empty()) return out << "<>";
    else {
        auto itr = s.begin();
        out << "<" << *itr;
        itr++;
        while (itr != s.end()) {
            out << ", " << *itr;
            itr++;
        }
        out << ">";
        return out;
    }
}

ll gcd(ll a, ll b) {
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    return b ? gcd(b, a % b) : a;
}

// a > b
ll gcdex(ll a, ll b) {
    return b ? gcdex(b, a % b) : a;
}

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

struct UFT {

public:
    ll tsize;
    ll mode;
    vl par;
    vl rank;

    UFT() {}

    UFT(const UFT &uft) {}

    UFT(ll tsizeget, ll modeget = 0) {
        tsize = tsizeget;
        mode = modeget;
        par.assign(tsize, -1);
        if (!mode) rank.resize(tsize, 0);
    }

    ll root(ll x) {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }

    bool isRoot(ll x) {
        return x == root(x);
    }

    bool same(ll x, ll y) {
        return root(x) == root(y);
    }

    void merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (mode) {
            par[x] += par[y];
            par[y] = x;
        } else {
            if (rank[x] < rank[y]) {
                par[y] += par[x];
                par[x] = y;
            } else {
                par[x] += par[y];
                par[y] = x;
                if (rank[x] == rank[y]) rank[x]++;
            }
        }
    }

    ll size(ll x) {
        return -par[root(x)];
    }
};

ll isP(ll n) {
    if (n <= 1) return 0;
    FOR(i, 2, (ll) sqrt(n) + 1) {
        if (n % i == 0) return 0;
    }
    return 1;
}

// https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
template<ll MOD>
struct Fp {
    long long val;

    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }

    constexpr ll getmod() { return MOD; }

    constexpr Fp operator-() const noexcept {
        return val ? MOD - val : 0;
    }

    constexpr Fp operator+(const Fp &r) const noexcept { return Fp(*this) += r; }

    constexpr Fp operator-(const Fp &r) const noexcept { return Fp(*this) -= r; }

    constexpr Fp operator*(const Fp &r) const noexcept { return Fp(*this) *= r; }

    constexpr Fp operator/(const Fp &r) const noexcept { return Fp(*this) /= r; }

    constexpr Fp &operator+=(const Fp &r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }

    constexpr Fp &operator-=(const Fp &r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }

    constexpr Fp &operator*=(const Fp &r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }

    constexpr Fp &operator/=(const Fp &r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }

    constexpr bool operator==(const Fp &r) const noexcept {
        return this->val == r.val;
    }

    constexpr bool operator!=(const Fp &r) const noexcept {
        return this->val != r.val;
    }

    friend constexpr ostream &operator<<(ostream &os, const Fp<MOD> &x) noexcept {
        return os << x.val;
    }

    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

using mint = Fp<MOD>;

vector<ll> fact, fact_inv, inv;
bool initedComb;

void initComb(ll size) {
    fact.resize(size + 5);
    fact_inv.resize(size + 5);
    inv.resize(size + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < size + 5; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
    initedComb = true;
}

long long comb(ll n, ll k) {
    if (!initedComb) {
        initComb(1e6);
    }
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

class DKnapsack1 {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        CIN(N,W);
        CINV(N,w,v);

        vvl dp(N+1,vl(W+1,0));

        REP(i,N){
            REP(j,W+1){
                if(j-w[i]>=0){
                    chmax(dp[i+1][j],dp[i][j-w[i]]+v[i]);
                }
                chmax(dp[i+1][j],dp[i][j]);
            }
        }
        COUT(dp[N][W]);
    }
};

































signed main() {
	DKnapsack1 solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);

    in.tie(0);
    ios::sync_with_stdio(0);
    out<<fixed<<setprecision(20);

    solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 80256