#include <bits/stdc++.h>

#define FILE_OP true
#define FILENAME "rucsac"

int solve() {
    int n, g;
    std::cin >> n >> g;
    std::vector<std::pair<int, int>> products(n + 1);

    for (int i = 1; i <= n; ++i) {
        int weight, profit;
        std::cin >> weight >> profit;
        products[i] = {weight, profit};
    }

    // dp[num][weight] = sum with first num elements and max weight of weight 
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(g + 1, 0));

    for (int i = 1; i <= n; ++i) {
        auto weight = products[i].first;
        auto profit = products[i].second;

        for (int j = 0; j <= g; ++j) {
            if (j < weight) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - weight] + profit);
            }
        }
    }

    return dp[n][g];

}

int main() {

    std::streambuf *coutbuf, *cinbuf;
    std::ifstream in;
    std::ofstream out;

    if (FILE_OP) {
        // Save original std::cin, std::cout
        coutbuf = std::cout.rdbuf();
        cinbuf = std::cin.rdbuf(); 

        in = std::ifstream(std::string(FILENAME) + ".in");
        out = std::ofstream(std::string(FILENAME) + ".out");

        //Read from infile.txt using std::cin
        std::cin.rdbuf(in.rdbuf());

        //Write to outfile.txt through std::cout 
        std::cout.rdbuf(out.rdbuf());   
    }

    std::cout << solve() << "\n";

    if (FILE_OP) {
        std::cin.rdbuf(cinbuf);   
        std::cout.rdbuf(coutbuf); 
    }
    return 0;
}