#include <bits/stdc++.h>
using namespace std;
struct node {
  long long l, r;
} a[200010];
long long n, s;
inline long long v_in() {
  char ch = getchar();
  long long sum = 0, f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) sum = (sum << 3) + (sum << 1) + (ch ^ 48), ch = getchar();
  return sum * f;
}
inline bool cmp(const node &a, const node &b) { return a.l < b.l; }
bool judge(long long x) {
  long long cnt = 0, k = s;
  for (register long long i = n; i >= 1; i--) {
    if (a[i].l >= x) {
      cnt++;
      if (cnt >= n / 2 + 1) return true;
      continue;
    }
    if (a[i].r >= x) {
      if (k >= x - a[i].l) {
        k -= x - a[i].l;
        cnt++;
        if (cnt >= n / 2 + 1) return true;
      }
    }
  }
  return false;
}
int main() {
  long long q = v_in();
  while (q--) {
    n = v_in(), s = v_in();
    long long lmin = 2000000000, rmax = 0;
    for (register long long i = 1; i <= n; i++) {
      a[i].l = v_in();
      s -= a[i].l;
      a[i].r = v_in();
      lmin = ((lmin) < (a[i].l) ? (lmin) : (a[i].l));
      rmax = ((rmax) > (a[i].r) ? (rmax) : (a[i].r));
    }
    sort(a + 1, a + n + 1, cmp);
    long long ans = 0, l = lmin, r = rmax;
    while (l <= r) {
      long long mid = (l + r) >> 1;
      if (judge(mid)) {
        ans = mid;
        l = mid + 1;
      } else
        r = mid - 1;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
