#include <fstream>
#include <time.h>
 
using namespace std;
 
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
 
int n, G, g[5001], p[5001], dp[3][10001];
 
int main()
{
   //double begin = clock();    
    
  fin >> n >> G;
   for (int i = 1; i <= n; i++)
     fin >> g[i] >> p[i];
  
  int a = 1, b = 2;
  
  int profit = 0;
  
  dp[1][g[1]] = p[1];
  
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j <= G; j++) {
      dp[b][j] = dp[a][j];
      
       if (j - g[i] >= 0)
         dp[b][j] = max (dp[b][j], dp[a][j - g[i]] + p[i]);
    }
    a = 3 - a;
    b = 3 - b;
  }
  
  for (int j = 0; j <= G; j++)
    profit = max (profit, dp[a][j]);
  fout << profit << endl;
  
  //double end = clock();
  
  //double f_time = double(end-begin) / CLOCKS_PER_SEC;
  
  //fout << f_time;
  
  return 0;
}