#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

int main() {
    ifstream infile("rucsac.in");
    ofstream outfile("rucsac.out");

    int N, G;
    infile >> N >> G;
    vector<int> weights(N);
    vector<int> profits(N);

    for (int i = 0; i < N; ++i) {
        infile >> weights[i] >> profits[i];
    }

    vector<int> dp(G + 1, 0);

    for (int i = 0; i < N; ++i) {
        for (int j = G; j >= weights[i]; --j) {
            dp[j] = max(dp[j], dp[j - weights[i]] + profits[i]);
        }
    }

    outfile << dp[G] << endl;

    infile.close();
    outfile.close();

    return 0;
}