#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>

using namespace std;
const int MAXINT = 2e9+20;

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

int dp[5001][10001];
int Cost[5001], Greutate[5001];

int knapsack(int N, int G){
  if(dp[N][G] != MAXINT) return dp[N][G];
  if(N == 0 || G == 0) return 0;
  if(Greutate[N] > G) return knapsack(N-1, G);
  int m = max(knapsack(N-1, G), knapsack(N-1, G-Greutate[N]) + Cost[N]);
  dp[N][G] = m;
  return m;
}

int main(){
  int N, G;
  in >> N >> G;
  for(int i = 1; i<=N; i++){
    in >> Greutate[i] >> Cost[i];
  }
  for(int i = 0; i<5001; i++)
    for(int j = 0; j<10001; j++)
      dp[i][j] = MAXINT;
  int result = knapsack(N, G);
  out << result;
  return 0;
}