#include <fstream>

int D[2][5002];

int main(){
  int N, G;
  std::ifstream fin("rucsac.in");
  std::ofstream fout("rucsac.out");

  fin >> N >> G;

  int W, P;

  for (int i = 0; i < N; i++){
    fin >> W >> P;

    for(int j = 1; j <= G; j++){
      if (j < W)
        D[i % 2][j] = i == 0 ? 0 : D[(i + 1) % 2][j];
      else
        D[i % 2][j] = std::max(i == 0 ? 0 : D[(i+1) % 2][j], i != 0 ? D[(i + 1) % 2][j - W] + P : P);
    }
  }

  fout << D[(N - 1) % 2][G] << "\n";

  return 0;
}