#include <fstream>
#define MaxG 10001
#define MaxN 5001
using namespace std;

int N, Wmax, maxP = 0;
int* elozo, *akt;
int T[2][MaxG];
int P[MaxN];
int W[MaxN];

void Beolvas()
{
    ifstream fin("rucsac.in");
    fin>>N>>Wmax;
    for (int i=1;i<=N;i++)
        fin>>W[i]>>P[i];
}

void Megold()
{
    elozo = T[0];
    akt = T[1];
    for (int i=1;i<=N;i++)
    {
        for (int w=0;w<=Wmax;w++)
        {
            if (w>=W[i])
                akt[w] = max(elozo[w], P[i]+elozo[w-W[i]]);
            else
                akt[w] = elozo[w];
        }
        swap(akt, elozo);
    }
    maxP = elozo[Wmax];
}

void Kiir()
{
    ofstream fout("rucsac.out");
    fout<<maxP;
}

int main()
{
    Beolvas();
    Megold();
    Kiir();
}