#include <bits/stdc++.h>
using namespace std;
long long n;
struct node {
  long long l, r;
} a1[200005], a2[200005], e[200005];
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
inline bool cmp1(node x, node y) { return x.r < y.r; }
inline bool cmp2(node x, node y) { return x.l < y.l; }
inline long long calc(long long x) {
  long long sum = 0, n1 = 0, n2 = 0;
  for (long long i = 1; i <= n; i++)
    if (e[i].r < x) sum += e[i].l, n1++;
  for (long long i = 1; i <= n; i++)
    if (e[i].l > x) sum += e[i].l, n2++;
  if (n1 > n / 2) return (1ll << 60);
  if (n2 > n / 2) return 0;
  long long tp = n / 2 - n1;
  for (long long i = 1; i <= n; i++)
    if (a1[i].l <= x && a1[i].r >= x) {
      if (tp)
        sum += a1[i].l, tp--;
      else
        sum += x;
    }
  return sum;
}
int main() {
  long long T = read();
  while (T--) {
    n = read();
    long long s = read();
    for (long long i = 1; i <= n; i++) {
      e[i].l = a1[i].l = a2[i].l = read();
      e[i].r = a1[i].r = a2[i].r = read();
    }
    sort(a1 + 1, a1 + n + 1, cmp2);
    if (n == 1) {
      cout << min(s, e[1].r) << endl;
      continue;
    }
    long long l = 1, r = (long long)(1e9), ans = 0;
    while (l <= r) {
      long long mid = l + r >> 1;
      if (calc(mid) <= s)
        ans = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    printf("%I64d\n", ans);
  }
  return 0;
}
