#include <fstream>
#include <vector>

using namespace std;

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

struct obj{
  int w, p;
};

const int NMAX = 5005;
const int GMAX = 10005;
int N, G;
int DP[2][GMAX];
vector <obj> v;

void Read(){
  int a, b;
  in >> N >> G;
  for(int i = 1; i <= N; ++i){
    in >> a >> b;
    obj aux = {a, b};
    v.push_back(aux);
  }
}

void Solve(){
  int p = 0;
  for(int i = 1; i <= N; ++i){
    for(int j = 1; j <= G; ++j){
      DP[p][j] = DP[!p][j];
      if(v[i - 1].w <= j){
        DP[p][j] = max(DP[p][j], DP[!p][j - v[i - 1].w] + v[i - 1].p);
      }
    }
    p = !p;
  }
  out << DP[!p][G] << "\n";
}

int main(){
  Read();
  Solve();
  return 0;
}