#include <fstream>
#define InFile  "rucsac.in"
#define OutFile "rucsac.out"
#define MAX1 5005
#define MAX2 10005

using namespace std;

void read ();
void solve ();
void print ();

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

int A[MAX2];
int i, j;

int Pmax;

int main ()
{
    read ();
    solve ();
    print ();
    return 0;
}

void read ()
{
    ifstream fin (InFile);
    fin >> N >> G;
    for (i=1; i<=N; i++)
        fin >> W[i] >> P[i];
}

void solve ()
{
    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]];
            }
}

void print ()
{
    ofstream fout (OutFile);
    fout << Pmax;
}