/* 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[2][Gmax],lin;

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