#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define Nm 5001
short N, Gmax;
short W[Nm], P[Nm];
int Cmax[2][10001];
int main()
{
    short i, g, z;


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

    z = 0;
    for(i = 1; i <= N; ++i)
    {
        for(g = 1; g <= Gmax; ++g)
        {
            Cmax[z][g] = Cmax[z * (-1) + 1][g];

            if(W[i] <= g && Cmax[z][g] < Cmax[z * (-1) + 1][g - W[i]] + P[i])
                Cmax[z][g] = Cmax[z * (-1) + 1][g - W[i]] + P[i];
        }

        z = z * (-1) + 1;
    }

    fout<<Cmax[z * (-1) + 1][Gmax];

    return 0;
}