#include<iostream>
#include<vector>
#include<fstream>

using namespace std;

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

    int N, G, i, j;
    in >> N >> G;

    //dp[i][j] = profitul maxim care se poate obtine pentru un rucsac
    //cu i obiecte si greutate j
    //vector<vector<int>> dp(N + 1, vector<int> (G + 1, 0));

    vector<int> w(N + 1);
    vector<int> p(N + 1);

    for (i = 1; i <= N; i++)
        in >> w[i] >> p[i];

    // for (j = 0; j <= G; j++)
    //     dp[0][j] = 0; //nu am obiecte, nu pot obtine niciun profit 
    
    // for (i = 1; i <= N; i++)
    //     for (j = 0; j <= G; j++)
    //         if (j - w[i] >= 0)
    //             dp[i][j] = max (dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
    //         else
    //             dp[i][j] = dp[i - 1][j];

   // out << dp[N][G];

   //VARIANTA OPTIMIZATA

   vector<int> dp(G + 1, 0);

   for (i = 1; i <= N; i++)
    for (j = G; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + p[i]);

    out << dp[G];
}