#include <fstream>

using namespace std;



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

    int dp[2][10001], W[5001], P[5001], N, G;

    fin >> N >> G;

    for(int i = 1; i <= N; ++i)
    {
        fin >> W[i] >> P[i];
    }

    for(int i = 0; i <= G; ++i)
    {
        dp[0][i] = dp[1][i] = 0;
    }

    bool row = 0;

    for(int i = 1; i <= N; ++i)
    {
        for(int j = 1; j < W[i]; ++j)
        {
            dp[row][j] = dp[!row][j];
        }

        for(int j = W[i]; j <= G; ++j)
        {
            dp[row][j] = max(dp[!row][j - W[i]] + P[i], dp[!row][j]);
        }

        row = !row;
    }

    fout << dp[!row][G];
}