//SOLUTIE EFICIENTA
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");

    int n, G;
    fin >> n >> G;

    vector<int> w(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++) {
        fin >> w[i] >> p[i];
    }

    vector<int> dp(G + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= G; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + p[i]);
        }
    }

    fout << dp[G];
    return 0;
}



//SOLUTIA ASTA PRIMESTE MEMORY TIME EXCEEDED

// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <algorithm>

// using namespace std;

// int main() {
//     ifstream fin("rucsac.in");
//     ofstream fout("rucsac.out");

//     int n, G;
//     fin >> n >> G;

//     vector<int> w(n + 1), p(n + 1);
//     for (int i = 1; i <= n; i++) {
//         fin >> w[i] >> p[i];
//     }

//     vector<vector<int>> dp(n + 1, vector<int>(G + 1));
//     for (int i = 0; i <= G; i++) {
//         dp[0][i] = 0;
//     }
//     for (int i = 1; i <= n; i++) {
//         for (int j = 0; j <= G; j++) {
//             if (j >= w[i]) {
//                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
//             } else {
//                 dp[i][j] = dp[i - 1][j];
//             }
//         }
//     }

//     fout << dp[n][G];
//     return 0;
// }