#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n;
long long s;
struct node {
  int l, r;
  bool operator<(const node& a) const { return l < a.l; }
} p[N];
vector<int> g;
int judge(long long x) {
  g.clear();
  long long sum = 0, cnt1 = 0, cnt2 = 0;
  for (int i = 1; i <= n; i++) {
    if (p[i].r < x)
      sum += p[i].l, cnt1++;
    else if (p[i].l > x)
      sum += p[i].l, cnt2++;
    else
      g.push_back(i);
  }
  if (cnt1 > n / 2) return 0;
  if (cnt2 > n / 2) return 1;
  for (int i = 0; i < n / 2 - cnt1; i++) {
    sum += p[g[i]].l;
  }
  sum += (n / 2 + 1 - cnt2) * x;
  if (sum <= s) return 1;
  return 0;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%lld", &n, &s);
    for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].l, &p[i].r);
    sort(p + 1, p + n + 1);
    long long left = 0, right = 1e9, mid, ans;
    while (right >= left) {
      mid = (left + right) >> 1;
      if (judge(mid))
        ans = mid, left = mid + 1;
      else
        right = mid - 1;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
