#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
void solve() {
  int n;
  LL s;
  scanf("%d%lld", &n, &s);
  vector<int> lb(n), ub(n);
  for (int i = 0; i < n; ++i) scanf("%d%d", &lb[i], &ub[i]);
  auto check = [&](int mid) -> int {
    multiset<LL> se;
    LL tot = 0;
    int need = (n - 1) / 2;
    for (int i = 0; i < n; ++i) {
      if (ub[i] < mid)
        --need, tot += lb[i];
      else if (lb[i] > mid)
        tot += lb[i];
      else
        se.insert(lb[i]);
    }
    if (need < 0) return 2;
    while (!se.empty() && need) {
      tot += *se.begin();
      se.erase(se.begin());
      --need;
    }
    if (need) return -1;
    tot += 1LL * mid * se.size();
    if (tot <= s)
      return 0;
    else
      return 1;
  };
  LL l = 1, r = 1e9;
  while (l + 1 < r) {
    LL m = (l + r) >> 1;
    int ret = check(m);
    if (ret < 0)
      l = m + 1;
    else if (ret > 0)
      r = m - 1;
    else
      l = m;
  }
  if (check(r) == 0)
    printf("%lld\n", r);
  else
    printf("%lld\n", l);
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) solve();
}
