#include <fstream>
#define InFile  "rucsac.in"
#define OutFile "rucsac.out"
#define MAX1 5001
#define MAX2 10001

using namespace std;

ifstream fin (InFile);
ofstream fout (OutFile);

unsigned short int N, G;
unsigned short int W[MAX1], P[MAX1];

unsigned int A[MAX2];
short int i, j;

unsigned int Pmax;

int main ()
{
    fin >> N >> 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 (A[j+W[i]] < A[j]+P[i])
            {
                A[j+W[i]] = A[j] + P[i];
                if (A[j+W[i]] > Pmax)
                    Pmax = A[j+W[i]];
            }
    fout << Pmax;
    return 0;
}