#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, s;
vector<pair<ll, ll>> v;
bool ok(ll x) {
  ll ns = 0, cnt = 0;
  vector<ll> vx;
  for (ll i = 0; i < n; ++i) {
    if (v[i].second < x) {
      ns += v[i].first;
    } else if (v[i].first >= x) {
      ns += v[i].first;
      cnt++;
    } else
      vx.push_back(v[i].first);
  }
  sort(vx.begin(), vx.end());
  ll tam = max(0LL, (n + 1LL) / 2LL - cnt);
  if (tam > vx.size()) return false;
  for (ll i = 0; i < vx.size(); ++i) {
    if (i < vx.size() - tam)
      ns += vx[i];
    else
      ns += x;
  }
  return ns <= s;
}
void solve() {
  cin >> n >> s;
  v = vector<pair<ll, ll>>(n);
  for (ll i = 0; i < n; ++i) {
    cin >> v[i].first >> v[i].second;
  }
  sort(v.begin(), v.end());
  ll lo = 1, hi = 1e9 + 10, mid;
  while (hi - lo > 1LL) {
    mid = (lo + hi) / 2LL;
    if (ok(mid)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  cout << lo << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
