#include <fstream>
#define NM 5010 // numarul de obiecte maxim posibil
#define GM 10010 // greutatea maxima posibila

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N; // numarul de obiecte
int G; // greutatea maxima admisa in rucsac
int i,j;
int GR[NM]; // greutatea fiecarui obiect
int P[NM]; // profitul adus de fiecare obiect
int DP[NM][GM];

/*
 * Voi aplica metoda programarii dinamice, tinand o matrice DP.
 *
 * DP[i][j] semnifica:
 * Profitul maxim pe care il pot obtine daca iau cateva obiecte din primele i obiecte date (ATENTIE pot sa le iau pe toate i, sau doar cateva (un SUBSET)),
 * iar obiectele luate avand greutatea totala j
 *
 * Voi numi de acum SUBSET al primelor i elemente, o multime M inclusa in multimea {1, 2, 3,..., i}
 * Voi numi STARE CURENTA pentru (i,j) elementul DP[i][j]
*/

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

    for (i=1; i<=N; i++)
        f >> GR[i] >> P[i]; // citesc greutatea si profitul aferent fiecarui obiect

    for (i=1; i<=N; i++) // parcurg in ordine obiectele
        for (j=1; j<=G; j++) // pentru fiecare i parcurg toate greutatile pe care le pot obtine
        {
            //Pentru DP[i][j] voi avea 2 posibilitati

            //1) DP[i][j]=DP[i-1][j], adica nu adaug obiectul i, deci profitul maxim obtinut dintr-un subset al primelor i obiecte, avand greutatea j
            // va fi defapt obtinut dintr-un SUBSET a primelor i-1 elemente
            DP[i][j]=DP[i-1][j];

            if (j>=GR[i]) // daca greutatea curenta este mai mare ca si greutatea obiectului i, atunci am posibilitatea ca pentru starea curenta sa iau in calcul si obiectul i
            {
                DP[i][j]=max(DP[i][j], DP[i-1][j-GR[i]] + P[i]);
                // DP[i][j] va fi maximul dintre valoarea setata anterior si
                // profitul maxim obtinut dintr-un SUBSET al primelor i-1 obiecte, avand greutatea totala j-GR[i], profit la care adaug profitul obiectului i
            }
        }

    int ANS=0;

    // caut raspunsul maxim printre DP[N][j], adica profitul maxim obtinut dintr-un SUBSET al celor N obiecte, avand totodata grija
    // ca greutatea totala a acestora sa nu depaseasca greutatea maxima admisa G

    for (j=1; j<=G; j++)
        ANS=max(ANS,DP[N][j]);

    g << ANS << '\n';

    f.close();
    g.close();

    return 0;
}