#include <iostream>
#define nmax 5001
#define gmax 10001
#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,g;
int a[nmax][gmax],gr[nmax],v[nmax];

int main()
{
    fin>>n>>g;

    for(int i=1;i<=n;i++)
        fin>>gr[i]>>v[i];

    /*
    matricea folosita va stoca:
    - pe linii numarul de obiecte i care pot fi luate;
    - pe coloane greutatea maxima care se admite la i obiecte;
    - in celula [i][j] profitul maxim care se poate obtine luand de la 0 la  i elemente ce au limita totala de masa j;
    */

    /*
    incepem parcurgerea pe linie, luan cate 1 obiect in plus din cele n obiecte.
    Pe parcurs decidem daca este posibila interventia acestuia (adica sa nu depaseasca limita de greutate) si daca
    e mai bine sa fie inclus in multime sau sa fie ignorat
    */

    for(int i=1;i<=n;i++)
    {
        //parcurgem fiecare coloana de greutate
        for(int j=1;j<=g;j++)
        {
            //initial, trecem datele anterioare (profitul maxim obtinut inainte la limita de greutate j, dar cu i-1 elemente)
            a[i][j]=a[i-1][j];

            //acum urmeaza sa decidem daca includem elementul(ne bazam pe greutatea acestuia)
            if(gr[i]<=j)
            {
                //decidem daca e mai bine sa il punem si pe el sau daca lasam profitul maxim anterior
                //Daca il punem pe el, ne raportam la alt profit, cel care permite includerea acestuia(ne limitam la greutate)
                a[i][j]=max(a[i-1][j],a[i-1][j-gr[i]]+v[i]);
            }

        }
    }

    /*
    afisarea valorilor matricii

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=g;j++)
            fout<<a[i][j]<<" ";
        fout<<endl;
    }
    */

    //valoarea maxima se va stoca in a[n][g], pentru ca anume acolo avem profitul maxim a obiectelor cu greutatea mai mica ca
    //limita maxima in limita a n obiecte (vorbim despre selectare de obiecte, ca nu le luam pe toate tot timpul);

    int vmax=a[n][g];
    fout<<vmax;

    return 0;
}