#include <bits/stdc++.h>
#include <fstream>

using namespace std;

const char iname[] = "rucsac.in";
const char oname[] = "rucsac.out";

int main() {
    ifstream in(iname);

    int N, W, i, j;
    int value, w;

    in >> N >> W;
    vector<int> prev(W + 1);
    vector<int> curr(W + 1);

    in >> w >> value;
    for (i = w; i <= W; ++i) {
        prev[i] = value;
    }

    for (i = 1; i <= N - 1; ++i) {
        in >> w >> value;
        for (j = 1; j <= W; ++j) {
            if (w > j) {
                curr[j] = prev[j];
            } else {
                curr[j] = max(value + prev[j - w], prev[j]);
            }
        }
        prev = curr;
    }

    in.close();

    ofstream out(oname);
    out << curr[W];
    out.close();

    return 0;
}