#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 Cost[5001], Greutate[5001];
int dp[2][10001];

int main(){
  int N, G;
  in >> N >> G;
  for(int i = 1; i<=N; i++){
    in >> Greutate[i] >> Cost[i];
  }
  for(int i = 1; i<=N; i++){
    for(int wg = 0; wg<=G; wg++){
      dp[1][wg] = dp[0][wg];
      if(Greutate[i] <= wg)
        dp[1][wg] = max(dp[0][wg], dp[0][wg-Greutate[i]] + Cost[i]);
    }
    for(int wg = 0; wg<=G; wg++)
      dp[0][wg] = dp[1][wg];
  }
  out  << dp[1][G];
}