/* Problema Rucsacului - O(N*G)
Se da o multime formata din N obiecte, fiecare fiind caracterizat de o greutate si un profit.
Sa se gaseasca o submultime de obiecte astfel incat suma profiturilor lor sa fie maxima,
iar suma greutatilor lor sa nu depaseasca o valoare G.
*/
#include <fstream>
#define Nmax 5009
#define Gmax 10009
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N,G,gr[Nmax],p[Nmax],D[Nmax][Gmax],k;

int main()
{
     f>>N>>G;
     for(int i=1;i<=N;++i) f>>gr[i]>>p[i];
     for(int i=1; i<=N ; ++i) // cu incerc sa fur primele i obiecte (1,..,i)
          for(int j=0; j<=G; ++j) //daca as avea un ghiozdan de capacitate j
          {
               // am doua variante
               //nu fur obiectul i
               D[i][j]=D[i-1][j];
               // il fur
               // daca pot sa bag obiectul i in ghiozdan
               if(gr[i]<=j)
                    D[i][j] = max(D[i][j], D[i-1][j-gr[i]]+p[i]);
          }
     g<<D[N][G]<<'\n';
     f.close();
     g.close();
     return 0;
}