/* 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,W[Nmax],P[Nmax],D[Gmax],sol;

int main()
{
     f>>N>>G;
     for(int i=1;i<=N;++i)f>>W[i]>>P[i];
     for(int i=1;i<=N;++i)
          for(int j=G-W[i];j>=0;--j)
          if(D[j+W[i]]<D[j]+P[i])
          {
               D[j+W[i]]=D[j]+P[i];
               if(sol<D[j+W[i]])sol=D[j+W[i]];
          }
     g<<sol<<'\n';
     return 0;
}