#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 5005, GMAX = 10005;
int N, G;
int W[NMAX], P[NMAX];
int D[GMAX];

int main()
{
    fin >> N >> G;

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

    D[0] = 0;
    int sol = 0;

    for(int i = 1; i <= N; ++i)
        for(int j = G - W[i]; j >= 0; --j)
        {
            if(D[j + W[i]] < D[j] + P[i])
            {
                D[j + W[i]] = D[j] + P[i];

                if(D[j + W[i]] > sol)
                    sol = D[j + W[i]];
            }
        }
    fout << sol;
}