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

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

    int dp[10001] = {0};

    for (int i = 1; i <= n; ++i) {
        for (int j = g; j >= obj[i].first; --j) {
            dp[j] = std::max(dp[j], dp[j - obj[i].first] + obj[i].second);
        }
    }
    output << dp[g];
    return 0;
}