#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > d;
long long s;
int f(int cost) {
  int cnt = 0;
  long long sum = 0;
  vector<int> vec;
  for (int i = 0; i < (int)d.size(); i++)
    if (cost <= d[i].first) {
      cnt++;
      sum += d[i].first;
    } else if (d[i].second < cost)
      sum += d[i].first;
    else if (d[i].first < cost && cost <= d[i].second)
      vec.push_back(d[i].first);
  int rem = max(0, ((int)d.size() + 1) / 2 - cnt);
  if (rem > (int)vec.size()) return false;
  for (int i = 0; i < (int)vec.size(); i++)
    if (i < (int)vec.size() - rem)
      sum += vec[i];
    else
      sum += cost;
  return sum <= s;
}
void solve() {
  int n;
  cin >> n >> s;
  d.clear();
  d.resize(n);
  for (int i = 0; i < n; i++) cin >> d[i].first >> d[i].second;
  sort(d.begin(), d.end());
  int l = 1, r = int(1e9) + 100;
  while (r - l > 1) {
    int mid = l + (r - l) / 2;
    if (f(mid))
      l = mid;
    else
      r = mid;
  }
  cout << l << endl;
}
int main() {
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}
