#include <bits/stdc++.h>
using namespace std;
long long n, s, curs;
const long long maxn = 2e5 + 10;
pair<long long, long long> vec[maxn];
long long v[maxn];
bool check(long long mid) {
  if (mid == s + 1) return false;
  long long sz = 0;
  for (long long i = 0; i < n; i++) {
    if (vec[i].second >= mid) v[sz++] = vec[i].first;
  }
  if (sz <= n / 2) return false;
  long long ans = 0;
  for (long long i = 1; i <= n / 2 + 1; i++) {
    if (v[sz - i] < mid) {
      ans += mid - v[sz - i];
    }
  }
  return ans <= curs;
}
int main() {
  long long t;
  scanf("%lld", &t);
  while (t--) {
    scanf("%lld%lld", &n, &s);
    curs = s;
    for (long long i = 0; i < n; i++) {
      long long a, b;
      scanf("%lld%lld", &a, &b);
      vec[i] = make_pair(a, b);
      curs -= vec[i].first;
    }
    sort(vec, vec + n);
    long long l = vec[n / 2].first, r = s + 1;
    while (r - l > 1) {
      long long mid = (r + l) >> 1;
      if (check(mid))
        l = mid;
      else
        r = mid;
    }
    cout << l << endl;
  }
}
