#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <regex>
#include <string>
#include <vector>

using namespace std;

using ll = long long;
using db = double;
using pi2 = pair<int, int>;
using pll2 = pair<ll, ll>;
using vs = vector<string>;
using vi = vector<int>;
using vi2 = vector<vi>;
using vi3 = vector<vi2>;
using vll = vector<ll>;
using vll2 = vector<vll>;
using vll3 = vector<vll2>;
using vd = vector<db>;
using vd2 = vector<vd>;
using vd3 = vector<vd2>;

#define int long long
#define mp makepair
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define PQ priority_queue
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, (n)-1)
#define FOR_IN(v, i) for (auto &(i) : (v))
#define ITOA(a, n) iota((a).begin(), (a).end(), n)
#define SORT_ASC(a) sort((a).begin(), (a).end())
#define SORT_DESC(a) sort((a).rbegin(), (a).rend())
#define UNIQUE(a) (a).erase(unique((a).begin(), (a).end()), (a).end())
#define PERM(a) next_permutation((a).begin(), (a).end())
#define PERM_DESC(a) prev_permutation((a).begin(), (a).end())
#define BINS(arr, tgt) binary_search((arr).begin(), (arr).end(), (tgt))
#define LB(arr, tgt)                                                           \
  (lower_bound((arr).begin(), (arr).end(), (tgt)) - (arr).begin())
#define UB(arr, tgt)                                                           \
  (upper_bound((arr).begin(), (arr).end(), (tgt)) - (arr).begin())
#define CNT(arr, tgt) count((arr).begin(), (arr).end(), (tgt))
#define SUM(arr) accumulate(arr.begin(), arr.end(), 0)
#define say(a) cout << (a) << " ";
#define echo(a) cout << (a) << endl;
#define YN(equation, if_t, if_f) echo((equation) ? (if_t) : (if_f))
#define SPACE say(" ")
#define TAB say("\t")
#define LF say("\n")
#define DigN2(a) (llabs(a) == 0 ? 1 : ((ll)(log2(db(llabs(a)))) + 1))
#define DigN10(a) (llabs(a) == 0 ? 1 : ((ll)(log10(db(llabs(a)))) + 1))
#define Dig2(a, b) (((a) >> (b)) & 1)
#define Dig10(a, b) (ll)(((a) / ((ll)(pow(10.0, (db)(b))))) % 10)
#define Pow2(n) (1 << (n))
#define Pow10(n) ((ll)(pow(10.0, db(n))))
#define LSB(a) ((a) & (-(a)))
#define iin(a)                                                                 \
  int(a);                                                                      \
  cin >> a;
#define llin(a)                                                                \
  ll(a);                                                                       \
  cin >> a;
#define strin(s)                                                               \
  string(s);                                                                   \
  cin >> s;
#define vin(v)                                                                 \
  FOR_IN((v), (i)) { cin >> i; };
#define vllin(v, N)                                                            \
  vll(v)((N));                                                                 \
  vin(v);
#define vsin(v, N)                                                             \
  vs(v)((N));                                                                  \
  vin(v);

static const ll inf = 1LL << 60;
static const ll MOD = 1e9 + 7;

class BIT {
public:
  vll d;
  vll v;
  ll size;
  BIT(ll _size) {
    size = _size;
    d.assign(size + 1, 0);
    v.assign(size, 0);
  }
  BIT(vll vec) { copy(vec); }
  void add(ll idx, ll N) {
    v[idx] += N;
    idx++;
    while (idx <= size) {
      d[idx] += N;
      idx += LSB(idx);
    }
  }

  ll sum(ll idx = inf) {
    idx++;
    idx = min(idx, size);
    ll ans = 0;
    while (idx) {
      ans += d[idx];
      idx -= LSB(idx);
    }
    return ans;
  }

  void copy(vll vec) {
    size = vec.size();
    d.assign(size + 1, 0);
    v.assign(size, 0);
    REP(i, size) { add(i, vec[i]); }
  }
};

class UnionFind {
public:
  vll arr;
  UnionFind(ll sz) : arr(sz, -1) {}
  ll root(ll node) {
    return arr[node] < 0 ? node : arr[node] = root(arr[node]);
  }
  ll size(ll x) { return -arr[root(x)]; }
  bool union_set(ll x, ll y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (arr[x] < arr[y]) {
        swap(x, y);
      }
      arr[x] += arr[y];
      arr[y] = x;
    }
    return x != y;
  }
  bool find_set(ll x, ll y) { return root(x) == root(y); }
};

class Vertex {
public:
  ll idx;
  ll param = -1;
  ll dist = inf;
  vector<pair<Vertex *, ll> /**/> e;
  ll size() { return e.size(); }
  bool operator==(const Vertex *o) { return dist == o->dist; }
  bool operator!=(const Vertex *o) { return dist != o->dist; }
  bool operator>(const Vertex *o) { return dist > o->dist; }
  bool operator<(const Vertex *o) { return dist < o->dist; }
  bool operator>=(const Vertex *o) { return dist >= o->dist; }
  bool operator<=(const Vertex *o) { return dist <= o->dist; }
};

class Graph {
public:
  vector<Vertex *> V;
  typedef tuple<Vertex *, Vertex *, ll> Edge;
  vector<Edge> E;
  Graph(ll sz) {
    REP(i, sz) {
      auto v = new Vertex();
      v->idx = i;
      V.pb(v);
    }
  }
  static bool comp(const Edge &e1, const Edge &e2) {
    return get<2>(e1) < get<2>(e2);
  }
  Vertex *getVertex(int idx) { return V[idx]; }
  void unite(ll from, ll to, ll w = 1, bool digraph = true) {
    E.push_back(make_tuple(V[from], V[to], w));
    V[from]->e.pb(make_pair(V[to], w));
    if (!digraph) {
      E.push_back(make_tuple(V[to], V[from], w));
      V[to]->e.pb(make_pair(V[from], w));
    }
  }
  void dijkstra(ll start) {
    PQ<Vertex *, vector<Vertex *>, greater<Vertex *> /**/> pq;
    Vertex *s = getVertex(start);
    s->dist = 0;
    pq.push(s);
    while (!pq.empty()) {
      Vertex *v = pq.top();
      pq.pop();
      for (auto &u : v->e) {
        if (u.first->dist > v->dist + u.second) {
          u.first->dist = v->dist + u.second;
          pq.push(u.first);
        }
      }
    }
  }
};

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

void vout(vll v) {
  say("{");
  REP(i, v.size()) {
    say(v[i]);
    if (i != v.size() - 1) {
      say(", ");
    }
  }
  echo("}");
}

ll DigS10(ll n) {
  ll m = 0;
  REP(i, DigN10(n)) { m += (ll)((llabs(n) % Pow10(i + 1))) / Pow10(i); }
  return m;
}

ll PowMod(ll a, ll b) {
  ll ans = 1, x = a % MOD;
  REP(i, DigN2(b)) {
    if (Dig2(b, i) == 1) {
      ans = (ans * x) % MOD;
    }
    if (i != (DigN2(b) - 1)) {
      x = (x * x) % MOD;
    }
  }
  return ans;
}

vll FactMod(1, 1);
vll FactModInv(1, 1);
ll Mod(ll n) {
  n %= MOD;
  n = (n + MOD) % MOD;
  return n;
}
ll InvM(ll n) {
  n = Mod(n);
  n = PowMod(n, MOD - 2);
  return n;
}
void CFactMod(ll n) {
  if (FactMod.size() <= n) {
    FOR(i, FactMod.size(), n) {
      FactMod.pb((FactMod[i - 1] * (i % MOD)) % MOD);
    }
  }
}
void CFactModInv(ll n) {
  CFactMod(n);
  if (FactModInv.size() < (n + 1)) {
    FactModInv.resize(n + 1, -1);
  }
  if (FactModInv[n] == -1) {
    FactModInv[n] = PowMod(FactMod[n], MOD - 2);
  }
  for (int i = n - 1; i >= 1; i--) {
    if (FactModInv[i] != -1)
      break;
    FactModInv[i] = ((FactModInv[i + 1] * ((i + 1) % MOD)) % MOD);
  }
}

ll CombMod(ll n, ll k) {
  if (n < 0 || k < 0 || n < k)
    return 0;
  if (n + 1 > FactModInv.size())
    CFactModInv(n);
  return ((((FactModInv[k] * FactModInv[n - k]) % MOD) * FactMod[n]) % MOD);
}

typedef tuple<long long, long long> Pair;

Pair factor_sub(long long n, long long m)
{
  long long i = 0;
  while (n % m == 0) {
    i++;
    n /= m;
  }
  return make_tuple(i, n);
}

vector<Pair> factorization(long long n)
{
  vector<Pair> a;
  long long c, m;
  tie(c, m) = factor_sub(n, 2);
  if (c > 0) a.push_back(make_tuple(2, c));
  for (long long i = 3; m >= i * i; i += 2) {
    tie(c, m) = factor_sub(m, i);
    if (c > 0) a.push_back(make_tuple(i, c));
  }
  if (m > 1) a.push_back(make_tuple(m, 1));
  return a;
}

signed main() {
  llin(N);
  llin(W);
  vll w, v;
  REP(i, N) {
    llin(a);
    w.pb(a);
    llin(b);
    v.pb(b);
  }
  vll2 dp;
  dp.resize(N + 1);
  REP(i, N + 1) {
    REP(j, W + 1) {
      dp[i].pb(0);
    }
  }
  FOR(i, 1, N) {
    FOR(j, 0, W) {
      if(j - w[i - 1] < 0) {
        dp[i][j] = dp[i - 1][j];
      } else {
      dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); // 0オリジンと1オリジンが混同しており悪．
      }
    }
  }
  echo(dp[N][W]);
}

Measured memory_bytes: 80120