#include <bits/stdc++.h>
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int rucsac(int n, int W, vector<int> w, vector<int> p) {

    vector<int> last(W + 1), current(W + 1);

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++)
            last[j] = current[j];

        for (int cap = 0; cap <= W; cap++) {
            current[cap] = last[cap];

            if (cap - w[i] >= 0) {
                int sol_aux = last[cap - w[i]] + p[i];

                current[cap] = max(current[cap], sol_aux);
            }
        }
    }

    return current[W];
}

int main() {
    int n, W;
    f >> n >> W;

    vector<int> w(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++)
        f >> w[i] >> p[i];
    g << rucsac(n, W, w, p);

    return 0;
}