#include <bits/stdc++.h>
const long long int inf = 9e18;
const long double pi = 2 * acos(0.0);
using namespace std;
long long int power(long long int a, long long int n) {
  if (n == 0) {
    return 1;
  }
  long long int p = power(a, n / 2) % 1000000007;
  p = (p * p) % 1000000007;
  if (n % 2 == 1) {
    p = (p * a) % 1000000007;
  }
  return p;
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
const int N = 1e6;
vector<long long int> sieve(N, 0);
void si() {
  sieve[1] = 1;
  for (int i = 2; i < N; i++) {
    if (sieve[i] == 0) {
      for (int j = i; j < N; j += i) {
        sieve[j] = i;
      }
    }
  }
}
long long int isprime(long long int n) {
  for (int i = 2; i < n; i++) {
    if (n % i == 0) {
      return 0;
    }
  }
  return 1;
}
long long int n, s;
int solve(vector<pair<long long int, long long int> > &a, long long int val,
          long long int s) {
  vector<pair<long long int, long long int> > v;
  int need = (n - 1) / 2;
  long long int tot = 0;
  int left = 0, right = 0;
  for (int i = 0; i < n; i++) {
    if (a[i].first < val && a[i].second < val) {
      left += 1;
      tot += a[i].first;
    } else if (a[i].first > val && a[i].second > val) {
      right += 1;
      tot += a[i].first;
    } else {
      v.push_back(make_pair(a[i].first, a[i].second));
    }
  }
  sort(v.begin(), v.end());
  if (left > need) {
    return -1;
  }
  if (right > need) {
    return -2;
  }
  int need1 = need - left;
  for (int i = 0; i < need1; i++) {
    tot += v[i].first;
  }
  int need2 = need - right + 1;
  for (int i = 0; i < need2; i++) {
    tot += val;
  }
  if (tot > s) {
    return -2;
  }
  return 1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> s;
    vector<long long int> L(n);
    vector<long long int> R(n);
    vector<pair<long long int, long long int> > a(n);
    for (int i = 0; i < n; i++) {
      cin >> L[i] >> R[i];
      a[i] = make_pair(L[i], R[i]);
    }
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());
    long long int l = L[n / 2];
    long long int r = R[n / 2];
    while (l <= r) {
      long long int mid = (l + r) / 2;
      if (solve(a, mid, s) == -1) {
        l = mid + 1;
      } else if (solve(a, mid, s) == -2) {
        r = mid - 1;
      } else {
        if (solve(a, mid + 1, s) == -1 || solve(a, mid + 1, s) == -2) {
          cout << mid << "\n";
          break;
        } else {
          l = mid + 1;
        }
      }
    }
  }
  return 0;
}
