#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 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, profit] = products[i];
        for (int j = 0; j <= g - weight; ++j) {
            dp[i][j + weight] = std::max(dp[i - 1][j + weight], dp[i - 1][j] + 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;
}