#include <fstream>
using namespace std;

long N,G;

long W[5005],P[5005];
long G1[10005],G2[10005];

long *L1,*L2;

long maxint(long a,long b)
{
 return (a > b) ? a : b;
}

int main(void)
{
 long i,g;
 fstream fin("rucsac.in",ios::in);
 fstream fout("rucsac.out",ios::out);
 fin >> N >> G;
 for (i = 0;i < N;i += 1)
  {
   fin >> W[i] >> P[i];
  }
 L1 = G1;
 L2 = G2;
 for (i = 0;i < N;i += 1)
  {
   for (g = 0;g <= G;g += 1)
    {
     if (W[i] <= g)
       {
        L2[g] = maxint(L1[g],L1[g - W[i]] + P[i]);
       }
      else
       {
        L2[g] = L1[g];
       }
    }
   long *t = L1;
   L1 = L2;
   L2 = t;
  }
 fout << L1[G];
 fin.close();
 fout.close();
 return 0;
}