#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 2e6 + 4;
const int N = 5e3 + 5;
const double eps = 1e-6;
const double pi = acos(-1);
long long qpow(long long x, long long y) {
  long long ans = 1;
  x %= mod;
  while (y) {
    if (y & 1) ans = ans * x % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
struct node {
  int l, r;
} a[maxn];
int _, n;
long long s;
bool cmp(node a, node b) { return a.l > b.l; }
bool ok(long long m) {
  long long cnt = 0, res = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i].l <= m && m <= a[i].r) {
      if (cnt < n / 2 + 1)
        res += m, cnt++;
      else
        res += a[i].l;
    } else {
      res += a[i].l;
      if (a[i].l >= m) cnt++;
    }
  }
  if (cnt < n / 2 + 1) return 0;
  return res <= s;
}
int main() {
  for (scanf("%d", &_); _; _--) {
    scanf("%d%lld", &n, &s);
    for (int i = 1; i <= n; i++) {
      scanf("%d%d", &a[i].l, &a[i].r);
    }
    sort(a + 1, a + 1 + n, cmp);
    long long l = 0, r = 1e9;
    long long ans = l;
    while (l <= r) {
      long long mid = l + r >> 1;
      if (ok(mid))
        l = mid + 1, ans = mid;
      else
        r = mid - 1;
    }
    printf("%lld\n", ans);
  }
}
