#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// namespace
using namespace std;
// type
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
// input
#define INIT              ({ ios::sync_with_stdio(false); cin.tie(0); })
#define VAR(type, ...)    type __VA_ARGS__; var_scan(__VA_ARGS__);
template<typename T>
static void var_scan(T& t)
{
    cin >> t;
}
template<typename T, typename... R>
static void var_scan(T& t, R&... rest)
{
    cin >> t;
    var_scan(rest...);
}
// output
#define OUT(var)          cout << (var)
#define SPC               cout << ' '
#define TAB               cout << '\t'
#define BR                cout << '\n'
#define ENDL              cout << endl
#define FLUSH             cout << flush
// debug
#ifdef DEBUG
#define EPRINTF(fmt, ...) fprintf(stderr, fmt, __VA_ARGS__)
#define DUMP(var)         cerr << #var << '\t' << (var) << '\n'
#define DUMPITERABLE(i) do {                            \
        cerr << #i << '\t';                             \
        for (const auto& it : i) { cerr << it << ' '; } \
        cerr << '\n';                                   \
} while (0)
#define DUMPITERABLE2(i2) do {                          \
        cerr << #i2 << '\t';                            \
        for (const auto& it : i2) {                     \
            for (const auto& it2: it) {                 \
                cerr << it2 << ' ';                     \
            }                                           \
        }                                               \
        cerr << '\n';                                   \
} while (0)
#else
#define EPRINTF(fmt, ...)
#define DUMP(var)
#define DUMPITERABLE(i)
#define DUMPITERABLE2(i)
#endif
// util
// [l, r)
#define REP(i, n)       for (int i = 0; i < (n); i++)
#define RREP(i, n)      for (int i = (n)-1; i >= 0; i--)
#define FOR(i, l, r)    for (int i = (l); i < (r); i++)
#define RFOR(i, r, l)   for (int i = (r)-1; i >= (l); i--)
#define REPLL(i, n)     for (ll i = 0; i < (n); i++)
#define RREPLL(i, n)    for (ll i = (n)-1; i >= 0; i--)
#define FORLL(i, l, r)  for (ll i = (l); i < (r); i++)
#define RFORLL(i, r, l) for (ll i = (r)-1; i >= (l); i--)

static constexpr int nmax = 100;
static constexpr int wmax = 100000;

int main(void)
{
    INIT;
    VAR(int, n, w);
    array<pair<int, int>, nmax> p;
    ll dp[n+1][w+1];
    fill_n(&dp[0][0], w+1, 0);
    REP(i, n) cin >> p[i].first >> p[i].second;
    FOR(i, 1, n+1){
        FOR(j, 0, w+1){
            dp[i][j] = j-p[i-1].first>=0? max(dp[i-1][j],dp[i-1][j-p[i-1].first]+p[i-1].second)
                                            : dp[i-1][j];
        }
    }
    OUT(dp[n][w]);
    ENDL;
    return 0;
}


Measured memory_bytes: 82504