#include <fstream>
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N, G, sol;
int Greutate[5001], Profit[5001];
int Optim[10001];

int main()
{
    f >> N >> G;
    for(int i = 1; i <= N; i++)
        f >> Greutate[i] >> Profit[i];
    Optim[0] = 0;
    for(int i = 1; i <= N; i++)
        for(int j = G - Greutate[i]; j >= 0; j--)
            if(Optim[j] + Profit[i] > Optim[j + Greutate[i]])
            {
                Optim[j + Greutate[i]] = Optim[j] + Profit[i];
                if(Optim[j + Greutate[i]] > sol)
                    sol = Optim[j + Greutate[i]];
            }
    g << sol;
    return 0;
}