#include <fstream>

#define NM1 5005
#define NM2 10005

using namespace std;

ifstream InF ("rucsac.in");
ofstream OutF ("rucsac.out");

int W[NM1], P[NM1];
int n, g;

int A[NM2];
int pmax, x;
int i, j;

void scan ();
void solve ();

int main ()
{
    scan ();
    solve ();
    OutF << x;
    return 0;
}

void scan ()
{
    InF >> n >> g;
    for (i=1; i<=n; i++)
        InF >> W[i] >> P[i];
}

void solve ()
{
    A[0] = 0;
    x = 0;
    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]] > x)
                    x = A[j+W[i]];
            }
}