#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> ara[200005];
int n;
long long s;
bool cheak(long long m) {
  long long rem = s;
  for (int i = 0; i < n; i++) rem -= ara[i].first;
  int p = (n + 1) >> 1;
  for (int i = 0; i < n && p; i++) {
    if (ara[i].first >= m)
      p--;
    else if (ara[i].second >= m && (m - ara[i].first) <= rem)
      rem -= (m - ara[i].first), p--;
  }
  return (!p);
}
long long mn, mx;
long long bs() {
  long long lo = mn, hi = mx, res;
  while (lo <= hi) {
    long long mid = (lo + hi) >> 1;
    if (cheak(mid))
      res = mid, lo = mid + 1;
    else
      hi = mid - 1;
  }
  return res;
}
int main() {
  int ts;
  scanf("%d", &ts);
  while (ts--) {
    scanf("%d %lld", &n, &s);
    mn = 1000000009;
    mx = 0;
    for (int i = 0; i < n; i++)
      scanf("%lld %lld", &ara[i].first, &ara[i].second),
          mn = min(mn, ara[i].first), mx = max(mx, ara[i].second);
    sort(ara, ara + n, greater<pair<long long, long long> >());
    printf("%lld\n", bs());
  }
  return 0;
}
