#include <bits/stdc++.h>
using namespace std;
struct node {
  int l, r;
} a[200009];
int n;
long long k;
bool cmp(node aa, node bb) {
  if (aa.l == bb.l)
    return aa.r < bb.r;
  else
    return aa.l < bb.l;
}
int check(int x) {
  long long ans = 0;
  int w = 0;
  for (int i = n; i >= 1; i--) {
    if (w <= n / 2) {
      if (a[i].r < x)
        ans += a[i].l;
      else {
        ans += max(a[i].l, x);
        w++;
      }
    } else {
      ans += a[i].l;
    }
  }
  if (w != (n / 2 + 1)) return 0;
  if (ans <= k)
    return 1;
  else
    return 0;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r);
    sort(a + 1, a + 1 + n, cmp);
    int l = 0, r = 1e9;
    while (l < r) {
      int mid = (l + r + 1) / 2;
      if (check(mid) == 1)
        l = mid;
      else
        r = mid - 1;
    }
    printf("%d\n", l);
  }
  return 0;
}
