#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct par {
  ll l;
  ll r;
};
int n;
ll s;
par mas[200100];
bool cmp(par a, par b) { return (a.l < b.l); }
bool good(ll m) {
  vector<par> grp1;
  vector<par> grp2;
  vector<par> grp3;
  for (int i = 0; i < n; i++) {
    if (mas[i].r < m)
      grp1.push_back(mas[i]);
    else if (m <= mas[i].l)
      grp2.push_back(mas[i]);
    else
      grp3.push_back(mas[i]);
  }
  int rem = max(0, (n + 1) / 2 - (int)grp2.size());
  if (rem > grp3.size()) return false;
  ll sum = 0;
  for (auto el : grp1) sum += el.l;
  for (auto el : grp2) sum += el.l;
  if (grp3.size() > 0) sort(grp3.begin(), grp3.end(), cmp);
  for (int i = 1; i <= rem; i++) sum += m;
  for (int i = 0; i < grp3.size() - rem; i++) sum += grp3[i].l;
  return (sum <= s);
}
ll bin_s() {
  ll l = 1, r = 1e9;
  ll m;
  while (l < r) {
    m = (l + r + 1) / 2;
    if (good(m))
      l = m;
    else
      r = m - 1;
  }
  return l;
}
void solve() {
  cin >> n >> s;
  for (int i = 0; i < n; i++) {
    cin >> mas[i].l >> mas[i].r;
  }
  ll med = bin_s();
  cout << med << '\n';
  return;
}
int main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
