#include <fstream>

using namespace std;

#define NMAX 10000
int d[NMAX + 1], dp[NMAX + 1];

int main(){
  ifstream fin ("rucsac.in");
  ofstream fout ("rucsac.out");

  int n, g, ans;
  ans = 0;
  fin >> n >> g;
  int w, p;
  for(int i = 1; i <= n; i++){
    fin >> w >> p;

    for(int j = 0; j <= g; j++){
      d[j] = dp[j];
      if(j >= w)
        d[j] = max(d[j], dp[j - w] + p);
    }
    for(int j = 0; j <= g; j++)
      dp[j] = d[j];
  }
  for(int i = 0; i <= g; i++)
    ans = max(ans, dp[i]);
  fout << ans;
  return 0;
}