#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    int dp[2][10010], w[5010], p[5010];
    long N, G, i, g, j;
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    in >> N >> G;
    for (i = 0; i < N; i++) in >> w[i] >> p[i];
    for (i = 0; i <= G; i++) dp[0][i] = 0;
    dp[0][0] = 0 ; dp[1][0] = 0;
    for (i = 0; i <= N-1; i++)
    {
        for (g = 1; g <= G; g++)
           if (g < w[i]) dp[1][g] = dp[0][g];
                else dp[1][g] = max (dp[0][g], dp[0][g-w[i]]+p[i]);
        for (g = 1 ; g <= G; g++)
            {dp[0][g] = dp[1][g] ; dp[1][g] = 0;}
        /*
        for (j = 0 ; j <= G; j++) out << dp[0][j] << " ";
        out << endl;
        */
    }
    out << dp[0][G];
    return 0;
}