#include <fstream>

using namespace std;

//Variabilele globale:
//m - matricea pe care facem dinamica
//g, p - vectorii cu greutatile, resprectiv preturile obiectelor
unsigned short int n,G,g[10001],p[5001];
unsigned int m[2][10001];

//Functia care determina maximul
unsigned short int max(unsigned short int a,unsigned short int b)
{
    if(a>b)
        return a;
    return b;
}

int main()
{
    //Dechiderea fisierelor
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");

    //Declararea contoarelor
    unsigned short int i=1,j=0;

    //Citirea numarului de obiecte si a capacitatii rucsacului
    fin>>n;
    fin>>G;

    //Citirea obiectelor
    for(;i<=n;i++)
    {
        fin>>g[i];
        fin>>p[i];
    }

    //Variabila folosita pentru a alterna liniile
    unsigned short int h=1;

    //Dinamica in O(N*G) si O(2*G) memorie
    for(i=n;i>=1;i--,h=1-h)
    {
        for(j=0;j<=G;j++)
        {
            if(j>=g[i])
            {
                m[h][j]=max(m[1-h][j],m[1-h][j-g[i]]+p[i]);
            }
            else
            {
                m[h][j]=m[1-h][j];
            }
        }
    }

    //Afisarea raspunsului
    fout<<m[1-h][G]<<'\n';

    //Incheiere
    fin.close();
    fout.close();

    return 0;
}