#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
long long t, n, m;
struct p {
  long long l, r;
  bool operator<(const p& tmp) const { return l < tmp.l; }
} a[maxn];
bool col(p a, p b) { return a.l < b.l; }
bool cor(p a, p b) { return a.r > b.r; }
bool isok(long long mid) {
  priority_queue<p> q;
  long long temp = 0, k = n / 2 + 1;
  for (int i = n; i >= 1; i--) {
    if (a[i].r >= mid && a[i].l <= mid)
      q.push(a[i]);
    else if (a[i].l > mid)
      temp += a[i].l, k--;
    else
      temp += a[i].l;
  }
  if (k < 0) return false;
  while (!q.empty()) {
    p u = q.top();
    q.pop();
    if (k)
      k--, temp += mid;
    else
      temp += u.l;
  }
  if (temp > m || k != 0)
    return false;
  else
    return true;
}
int main() {
  cin >> t;
  while (t--) {
    long long l = 1e9, r = 0, ans = -1;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
    sort(a + 1, a + 1 + n, col);
    l = a[n / 2 + 1].l;
    sort(a + 1, a + 1 + n, cor);
    r = a[n / 2 + 1].r;
    while (r >= l) {
      long long mid = l + r >> 1;
      if (isok(mid))
        l = mid + 1, ans = mid;
      else
        r = mid - 1;
    }
    cout << ans << endl;
  }
}
