#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int maxn = 2e6 + 100;
const int maxm = 2e6 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
int t;
pair<long long, long long> a[maxn];
long long s;
int n;
int vis[maxn];
bool cmp2(pair<long long, long long> a, pair<long long, long long> b) {
  return a.second < b.second;
}
vector<long long> mm, rr, lll;
int ck(long long x) {
  int L = 0, R = 0, M = 0;
  lll.clear();
  rr.clear();
  mm.clear();
  for (int i = 1; i <= n; i++) {
    if (a[i].first <= x && a[i].second >= x) {
      mm.push_back(a[i].first);
      M++;
      continue;
    }
    if (a[i].first > x) {
      R++;
      rr.push_back(a[i].first);
    }
    if (a[i].second < x) {
      L++;
      lll.push_back(a[i].first);
    }
  }
  if (L > n / 2) return false;
  long long res = 0;
  sort(mm.begin(), mm.end());
  if (L < n / 2) {
    int to = M;
    for (int i = 0; i < to; i++) {
      lll.push_back(mm[i]);
      L++;
      M--;
      if (L == n / 2) break;
    }
  }
  if (R < n / 2 + 1) {
    if (R + M != n / 2 + 1) return false;
    res += 1ll * M * x;
  }
  for (int i = 0; i < (int)lll.size(); i++) {
    res += lll[i];
  }
  for (int i = 0; i < (int)rr.size(); i++) {
    res += max(rr[i], x);
  }
  return res <= s;
}
int main() {
  scanf("%d", &t);
  while (t--) {
    long long mx = 0;
    scanf("%d %lld", &n, &s);
    for (int i = 1; i <= n; i++) {
      scanf("%lld %lld", &a[i].first, &a[i].second);
      mx = max(mx, a[i].second);
    }
    long long ans = 0;
    sort(a + 1, a + 1 + n);
    long long l = a[n / 2 + 1].first;
    sort(a + 1, a + 1 + n, cmp2);
    long long r = a[n / 2 + 1].second;
    while (l <= r) {
      long long mid = l + r >> 1;
      if (ck(mid)) {
        l = mid + 1;
        ans = mid;
      } else
        r = mid - 1;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
