// {{{ Headers
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}

#include <cassert>
#include <cctype>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#include <fstream>
#include <iostream>
#include <sstream>

using namespace std;
// }}}

typedef long long int64;
const int INF = 0x3f3f3f3f;
template <class T> inline int len (const T &a) { return a.size (); }
#define ALL(x) (x).begin(), (x).end()

// {{{ Unused templates and debug
const double EPS = 1e-9;
const double PI = 3.14159265358979323846264338328;
const long long LINF = (long long) 1e16 + 5;

template <class T> inline int toInt (const T& t) { int n; stringstream ss; ss << t; ss >> n; return n; }
template <class T> inline string toStr (const T& t) { stringstream ss; ss << t; return ss.str(); }
template <class T> inline int64 toInt64 (const T& t) { int64 n; stringstream ss; ss << t; ss >> n; return n; }
template <typename T> int sgn (T val) { return (T(0) < val) - (val < T(0)); }
template <class T> T gcd (T a, T b) { T r; while (b) { r = a % b; a = b; b = r; } return a; }
template <class T> T lcm (T a, T b) { return a / gcd (a, b) * b; }

// Overloading ostream for printing STL containers (pair, vector, set, map)
template <typename T1, typename T2>
inline std::ostream &operator << (std::ostream &os, const std::pair <T1, T2> &p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
inline std::ostream &operator << (std::ostream &os, const std::vector <T> &v) {
    bool first = true;
    os << "[";
    for (unsigned int i = 0; i < v.size(); i++) {
        if (! first)
            os << ", ";
        os << v[i];
        first = false;
    }
    return os << "]";
}
template <typename T>
inline std::ostream &operator << (std::ostream &os, const std::set <T> &S) {
    bool first = true;
    os << "set([";
    for (typename std::set <T>::const_iterator it = S.begin(); it != S.end(); ++it) {
        if (! first)
            os << ", ";
        os << *it;
        first = false;
    }
    return os << "])";
}
template <typename T1, typename T2>
inline std::ostream &operator << (std::ostream &os, const std::map <T1, T2> &d) {
    bool first = true;
    os << "{";
    for (typename std::map<T1, T2>::const_iterator it = d.begin(); it != d.end(); ++it) {
        if (! first)
            os << ", ";
        os << it->first << ": " << it->second;
        first = false;
    }
    return os << "}";
}

// Color codes for highlighting debugs.
// Does not work within macvim due to dumb terminal.
#ifdef MVIM
    #define COLOR_CLEAR ""
    #define COLOR_RED ""
    #define COLOR_GREEN ""
    #define COLOR_MAGENTA ""
    #define COLOR_CYAN ""
#else
    #define COLOR_CLEAR "\033[0m"
    #define COLOR_RED "\033[31m"
    #define COLOR_GREEN "\033[32m"
    #define COLOR_MAGENTA "\033[35m"
    #define COLOR_CYAN "\033[36m"
#endif

// A macro to print statement and execute it.
#define exec(args...) cerr << COLOR_CYAN << #args << '\n' << COLOR_CLEAR; args

// A macro to print arrays.
#define print(arr, _N) { cerr << COLOR_RED << ">>> " << #arr << " " << #_N << COLOR_CLEAR << " #--> "; for (int _i = 0; _i < _N; _i++) cerr << arr [_i] << " "; putchar ('\n'); }

// A macro to print 2d arrays.
#define print2(arr, _R, _C) { cerr << COLOR_RED << ">>> " << #arr << " " << #_R << " " << #_C << COLOR_CLEAR << " #-->\n";\
    for (int _i = 0; _i < _R; _i++) { \
        for (int _j = 0; _j < _C; _j++) cerr << arr [_i][_j] << " ";\
        putchar ('\n'); } };

// debug () can print vector, set, map, pairs etc now.
#define debug(args...) { cerr << COLOR_RED << ">>> " << #args << COLOR_CLEAR << " #--> "; dbg, args; cerr << endl; }
struct debugger {
    template <typename T> debugger& operator, (const T v) {
        cerr << v << " ";
        return *this;
    }
} dbg;

// Getting rid of %lld vs %I64d on *nix vs win platform.
#if (_WIN32 || __WIN32__)
#  define LLD "%I64d"
#else
#  define LLD "%lld"
#endif
// }}}

int64 dp [105][100 * 1000 + 5];
int v [100 * 1000 + 5];
int w [100 * 1000 + 5];
int N, W;

int
main () {
    scanf ("%d %d", &N, &W);
    for (int i = 0; i < N; i++) scanf ("%d %d", w + i, v + i);
    memset (dp, 0, sizeof (dp));
    for (int i = 1; i <= N; i++)
        for (int j = 0; j <= W; j++) {
            dp [i][j] = max (dp [i][j], dp [i - 1][j]);
            if (j - w [i - 1] >= 0)
                dp [i][j] = max (dp [i][j], v [i - 1] + dp [i - 1][j - w [i - 1]]);
        }

    int64 ret = 0;
    for (int i = 0; i <= W; i++) ret = max (ret, dp [N][i]);
    printf ("%lld\n", ret);


#ifdef LOCALHOST
	cerr << "time: " << (int64) clock () * 1000 / CLOCKS_PER_SEC << " ms" << endl;
#endif
    return 0;
}



Measured memory_bytes: 82304