#include <iostream>
#include <fstream>

int dp[2][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;
    }
    int row = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= g; ++j) {
            dp[row][j] = dp[1 - row][j];
            if (obj[i].first <= j) dp[row][j] = std::max(dp[row][j], dp[1 - row][j - obj[i].first] + obj[i].second);
        }
        row = 1 - row;
    }

    output << dp[1 - row][g];

    return 0;
}