#include <iostream>
#include <fstream>

int main() {
    std::ifstream input("rucsac.in");
    std::ofstream output("rucsac.out");
    int n, g;
    input >> n >> g;
    int w[5001], v[5001];
    for (int i = 1; i <= n; ++i) {
        input >> w[i] >> v[i];
    }

    int dp[10001] = {0};

    for (int i = 1; i <= n; ++i) {
        for (int j = g; j >= w[i]; --j) {
            if (dp[j - w[i]] + v[i] > dp[j]) {
                dp[j] = dp[j - w[i]] + v[i];
            }
        }
    }
    output << dp[g];
    return 0;
}