#include <iostream>
#include <fstream>

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 prices[2][10001] = {0};

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= g; ++j) {
            prices[1][j] = prices[0][j];

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