#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

const int NMAX = 5e3 + 3;
const int GMAX = 1e4 + 3;

int N, G;
int dp[2][GMAX];
int W[NMAX];
int P[NMAX];

int mymax(int a, int b)
{
   return (a > b ? a : b);
}

int main()
{
   fin >> N >> G;

   for(int i = 1; i <= N; ++i)
      fin >> W[i] >> P[i];

   dp[1][W[1]] = P[1];
   for(int i = 2; i <= N; ++i) {
      int level = (i & 1);
      int last = (i + 1) % 2;

      for(int j = 1; j <= G; ++j)
         if(j >= W[i])
            dp[level][j] = mymax(dp[last][j], dp[last][j - W[i]] + P[i]);
         else dp[level][j] = dp[last][j];

   }

   fout << dp[(N & 1)][G] << '\n';
   return 0;
}