#include <bits/stdc++.h>
using namespace std;
std::mt19937 rng(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
const double EPS = 1e-9;
const double PI = acos(-1);
const int MOD = 1000000007;
vector<pair<long long, long long> > v;
int n;
long long s;
bool test(long long x) {
  long long sum = 0;
  for (int i = 0; i < n; i++) sum += v[i].first;
  int cont = 0;
  for (int i = n - 1; i >= 0 and cont < (n + 1) / 2; i--) {
    if (x <= v[i].second) {
      sum += max(0LL, x - v[i].first);
      cont++;
    }
  }
  return sum <= s and cont == (n + 1) / 2;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> s;
    v.resize(n);
    for (int i = 0; i < n; i++) {
      cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end());
    long long lo = 0, hi = MOD, ans = -1LL;
    while (lo <= hi) {
      long long mi = (lo + hi) / 2LL;
      if (test(mi)) {
        ans = mi;
        lo = mi + 1;
      } else {
        hi = mi - 1;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}
