#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;
    }

    int new_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 {
                new_value = value + prev[j - w];
                if (new_value > prev[j]) {
                    curr[j] = new_value;
                } else {
                    curr[j] = prev[j];
                }
            }
        }
        prev = curr;
    }

    in.close();

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

    return 0;
}