#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 5005;
const int Gmax = 10005;

int N, G;
int wg[Nmax], pr[Nmax];
int M[Nmax][Gmax];

void read()
{
   ifstream f("rucsac.in");
   f >> N >> G;
   for(int i = 1; i <= N; i ++)
   {
      f >> wg[i] >> pr[i];
   }
   f.close();
}

void Backpack()
{
   for(int i = 1; i <= N; i ++)
   {
      for(int j = 1; j <= G; j ++)
      {
         M[i][j] = M[i-1][j];
         if(wg[i] <= j)
         {
            M[i][j] = max(M[i-1][j], M[i-1][j-wg[i]]+pr[i]);
         }
      }
   }
}

void print()
{
   ofstream g("rucsac.out");
   g << M[N][G];
   g.close();
}

int main()
{
    read();
    Backpack();
    print();
    return 0;
}