#include <fstream>

using namespace std;
int W[5001], P[5001];
int Optim[10001];
int main()
{
    ifstream fin ("rucsac.in");
    ofstream fout ("rucsac.out");
    register int i;
    register int j;
    int N, G, sol=0;
    fin >> N;
    fin >> G;
    for (i = 1; i <= N; ++i)
        fin >> W[i] >> P[i];
    for(i = 1; i <= N; ++i)
        for(j = G - W[i]; j >= 0; --j)
        {
            if( Optim[j+W[i]] < Optim[j] + P[i] )
            {
                Optim[j+W[i]] = Optim[j] + P[i];
                if( Optim[j+W[i]] > sol)
                    sol = Optim[j+W[i]];
            }
        }
    fout << sol;
    return 0;
}