#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int N, G;
    fin >> N >> G;
    vector<int> W(N + 1), P(N + 1);
    for (int i = 1; i <= N; ++i) {
        fin >> W[i] >> P[i];
    }
    vector<int> dp(G + 1, 0);
    for (int i = 1; i <= N; ++i) {
        for (int cw = G; cw >= W[i]; --cw) {
            dp[cw] = max(dp[cw], dp[cw - W[i]] + P[i]);
        }
    }
    fout << dp[G] << endl;
    return 0;
}