#include <iostream>
#include <fstream>

int dp[1001][10001] = {0};

int main() {
    std::ifstream input("rucsac.in");
    std::ofstream output("rucsac.out");

    int n, g;

    input >> n >> g;

    std::pair<int, int> obj[1001] = {{}};

    for (int i = 1; i <= n; ++i) {
        input >> obj[i].first >> obj[i].second;
    }

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

    output << dp[n][g];

    return 0;
}