#include <iostream>
#include <fstream>
using namespace std;

int n,C; // n-nr de obiecte; C-capacitatea rucsacului
int greutate[5001],profit[5001];
/* greutate[i]= greutatea obiectului i
   profit[i]= profitul adus de obiectul i
*/
//int Solutie[5001][10001];//aici calculez solutia problemei
//Solutie[n][C] = solutia problemei

int solutie[10001];


int maxim(int a,int b)
{
    return a > b ? a : b;
}


int calculeazaSolutieVector()
{
    //Problema rucsacului - abordare top-down folosind un vector unidimensional
     for(int i=1;i<=n;i++) // pentru fiecare obiect din cele n posibile
     {
        for(int j=C-greutate[i];j>=0;--j) // pentru toate greutatile mai putin greutatea obiectului i
        {
            /* daca luand in considerare obiectul i ( solutie[j] + profit[i] )
             se obtine un profit MAI MARE decat neluand in considerare obiectul i (solutie[j+greutate[i]])
             atunci inlocuieste
             */
           if(solutie[j+greutate[i]] < solutie[j] + profit[i])
            {
                solutie[j+greutate[i]] = solutie[j] + profit[i];

            }
        }
    }
    return solutie[C];

}

/*
int calculeazaSolutieMatrice()
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<=C;j++)
            if(j>=greutate[i])//daca am loc in rucsac pentru obiectul i
            {
                Solutie[i][j] = maxim ( Solutie[i-1][j],Solutie[i-1][j-greutate[i]]+profit[i]);
                 Solutie[i-1][j] = solutia problemei fara a alege obiectul i
                  Solutie[i-1][j-greutate[i]]+profit[i] = solutia pb din profitul adus de obiectul i(profit[i])
                  si cea mai buna solutie fara greutatea obiectului i( adica Solutie[i-1][j-greutate[i]] )
                */
           /* }
            else //nu am loc in rucsac
                Solutie[i][j]=Solutie[i-1][j];// adica cea mai buna solutie fara obiectul i

   return Solutie[n][C];
}
*/


int main()
{
    ifstream in("rucsac.in");
    in>>n>>C;
    for(int i=1;i<=n;++i)
        in>>greutate[i]>>profit[i];
    in.close();
    ofstream out("rucsac.out");
    //out<<calculeazaSolutieMatrice()<<"\n";
    out<<calculeazaSolutieVector();
    out.close();
    return 0;
}