#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 6;
const long long MOD2 = 1e9 + 7;
const long long MOD = 998244353;
long long s;
pair<long long, long long> a[N];
int n;
int qan;
bool check(long long v) {
  long long ans = 0;
  qan = n / 2 + 1;
  for (int i = (n)-1; i >= 0; i--) {
    if (a[i].first > v && qan) {
      ans += a[i].first;
      qan--;
    } else if (a[i].first <= v && v <= a[i].second && qan) {
      ans += v;
      qan--;
    } else {
      ans += a[i].first;
    }
  }
  if (qan == 0 && ans <= s) return true;
  return false;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int ttt;
  cin >> ttt;
  while (ttt--) {
    cin >> n >> s;
    for (int i = 0; i < (n); ++i) {
      cin >> a[i].first >> a[i].second;
    }
    sort(a, a + n);
    int l = 0, r = 1e9 + 1;
    while (l < r) {
      int md = (l + r) / 2;
      if (check(md)) {
        l = md + 1;
      } else {
        r = md;
      }
    }
    cout << l - 1 << endl;
  }
  return 0;
}
