#include <fstream>
using namespace std;

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

int greutati[5005], profituri[5005], solutii[2][10005];

int main()
{
    int N, G, greutate, profit, current_line = 0, previous_line, maximum = 0;
    fin >> N >> G;
    for (int i = 1; i <= N; i++)
    {
        fin >> greutate >> profit;
        greutati[i] = greutate;
        profituri[i] = profit;
    }
    for (int i = 1; i <= N; i++)
    {
        current_line = 1 - current_line;
        previous_line = 1 - current_line;
        for (int j = 0; j <= G; j++)
        {
            solutii[current_line][j] = solutii[previous_line][j];
            if (greutati[i] <= j)
            {
                solutii[current_line][j] = max(solutii[previous_line][j], solutii[previous_line][j - greutati[i]] + profituri[i]);
            }
        }
    }
    for (int i = 0; i <= G; i++)
    {
        maximum = max(solutii[current_line][i], maximum);
    }
    fout << maximum << "\n";
    return 0;
}