#include <bits/stdc++.h>
using namespace std;
const long long int N = 5e5 + 5, mod = 1000000007, bit = 60;
bool comp(pair<long long int, long long int> &a,
          pair<long long int, long long int> &b) {
  if (a.second != b.second) {
    return a.second < b.second;
  }
  return a.first < b.first;
}
bool comp1(pair<long long int, long long int> &a,
           pair<long long int, long long int> &b) {
  if (a.first != b.first) {
    return a.first < b.first;
  }
  return a.second < b.second;
}
bool check(long long int mid, long long int k,
           vector<pair<long long int, long long int> > &p) {
  long long int n = p.size(), cost = 0, i, compulsory = 0, need, rem;
  vector<pair<long long int, long long int> > v;
  for (i = 0; i < n; i++) {
    if (p[i].second < mid) {
      cost += p[i].first;
    } else if (p[i].first >= mid) {
      compulsory++;
      cost += p[i].first;
    } else {
      v.push_back({p[i].first, p[i].second});
    }
  }
  need = max(0ll, ((n + 1) >> 1) - compulsory);
  if (v.size() < need) {
    return 0;
  }
  rem = v.size() - need;
  sort(v.begin(), v.end(), comp1);
  reverse(v.begin(), v.end());
  while (rem--) {
    cost += v.back().first;
    if (v.back().first > mid) {
      return 0;
    }
    v.pop_back();
  }
  while (need--) {
    cost += max(mid, v.back().first);
    if (v.back().second < mid) {
      return 0;
    }
    v.pop_back();
  }
  return cost <= k;
}
signed main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long int pro = 1, temp, t, i, j, l, r, n, m, mid, z, k, x, y, rem,
                carry = 0, ind, ans = 0, mx = -LONG_LONG_MAX,
                mn = LONG_LONG_MAX, cnt = 0, curr = 0, prev, next, sum = 0,
                flag = 1, i1 = -1, i2 = -1;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    vector<pair<long long int, long long int> > p(n);
    for (i = 0; i < n; i++) {
      cin >> p[i].first >> p[i].second;
    }
    sort(p.begin(), p.end());
    l = p[n / 2].first;
    sort(p.begin(), p.end(), comp);
    r = p[n / 2].second;
    while (l <= r) {
      mid = (l + r) >> 1;
      if (check(mid, k, p)) {
        ans = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}
