#include <bits/stdc++.h>
using namespace std;
struct range {
  int l, r, id;
} rng[200010];
int vis[200010];
int n;
long long s;
bool find(int m) {
  for (int i = 1; i <= n; i++) vis[i] = 0;
  int lcnt(0), rcnt(0);
  long long sum(0);
  for (int i = 1; i <= n; i++) {
    if (rng[i].r < m) {
      lcnt++;
      sum += rng[i].l;
      vis[i] = 1;
    } else if (rng[i].l > m) {
      rcnt++;
      sum += rng[i].l;
      vis[i] = 1;
    }
    if (sum > s || lcnt > n / 2 || rcnt > n / 2) return false;
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    if (lcnt < n / 2) {
      if (rng[i].l > m) {
        return false;
      }
      sum += rng[i].l;
      lcnt++;
      vis[i] = 1;
    } else if (rcnt <= n / 2) {
      sum += m;
      vis[i] = 1;
      rcnt++;
    }
    if (sum > s) return false;
  }
  return true;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %I64d", &n, &s);
    for (int i = 1; i <= n; i++) {
      scanf("%d %d", &rng[i].l, &rng[i].r);
      rng[i].id = i;
    }
    sort(rng + 1, rng + 1 + n,
         [](const range& lhs, const range& rhs) { return lhs.r < rhs.r; });
    int r = rng[n / 2 + 1].r + 1;
    sort(rng + 1, rng + 1 + n,
         [](const range& lhs, const range& rhs) { return lhs.l < rhs.l; });
    int l = rng[n / 2 + 1].l;
    while (r - l > 1) {
      int m = (l + r) >> 1;
      if (find(m)) {
        l = m;
      } else {
        r = m;
      }
    }
    printf("%d\n", l);
  }
}
