#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
const int M = 1e9 + 7;
vector<pair<int, int> > seg;
bool check(long long n, long long s, long long median) {
  long long less = 0, more = 0;
  long long cur = 0;
  vector<int> v;
  for (int i = 0; i < n; i++) {
    if (seg[i].second < median) {
      cur += seg[i].first;
    } else if (median <= seg[i].first) {
      cur += seg[i].first;
      more++;
    } else {
      v.push_back(seg[i].first);
    }
  }
  sort(v.begin(), v.end(), greater<int>());
  int rem = max(0LL, (n + 1) / 2 - more);
  if ((int)v.size() < rem) return false;
  for (auto val : v) {
    if (rem > 0) {
      cur += median;
      rem--;
    } else {
      cur += val;
    }
  }
  return cur <= s;
}
void solve() {
  long long n, s;
  cin >> n >> s;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    seg.push_back({x, y});
  }
  sort(seg.begin(), seg.end());
  long long lo = seg[n / 2].first, hi = s + 1;
  while (hi - lo > 1) {
    long long mid = lo + hi >> 1;
    if (check(n, s, mid))
      lo = mid;
    else
      hi = mid;
  }
  cout << lo << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
    seg.clear();
  }
  return 0;
}
