#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 2e5 + 5;

int n, c;
std::pair<int, int> a[kMaxN];

bool check(int t) {
  static std::pair<int, int> b[kMaxN];
  static int tmp[kMaxN];
  __int128_t now = (__int128_t)t * c;
  for (int i = 1; i <= n; ++i) {
    b[i] = a[i];
    int cnt = std::min<__int128_t>({t, now, (b[i].second - 1) / b[i].first});
    b[i].second -= b[i].first * cnt;
    now -= cnt;
    tmp[i] = cnt;
  }
  if (now) {
    std::vector<std::pair<int, int>> vv;
    for (int i = 1; i <= n; ++i) {
      if (tmp[i] < t)
        vv.emplace_back(b[i].second, i);
    }
    std::sort(vv.begin(), vv.end(), std::greater<>());
    for (auto [val, i] : vv) {
      if (now) {
        b[i].second = 0, --now;
      }
    }
  }
  // for (int i = 1; i <= n; ++i) std::cerr << b[i].first << ' ' << b[i].second << '\n';
  // std::cerr << (int)now << '\n';
  std::vector<int> vec;
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    sum += b[i].second;
  }
  for (int i = 1; i <= n; ++i) {
    vec.emplace_back(std::min(b[i].first, b[i].second));
    // vec.emplace_back(b[i].first, b[i].second / b[i].first);
    // vec.emplace_back(b[i].second % b[i].first, 1);
  }
  std::sort(vec.begin(), vec.end(), std::greater<>());
  for (auto x : vec) sum = std::min(sum, sum - x + 1);
  return sum <= c;
}

void dickdreamer() {
  std::cin >> n >> c;
  for (int i = 1; i <= n; ++i) std::cin >> a[i].second >> a[i].first;
  std::sort(a + 1, a + 1 + n, std::greater<>());
  int L = -1, R = 1e18, res = 1e18;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (check(mid)) R = res = mid;
    else L = mid;
  }
  std::cout << res << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}