#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 2;
pair<long long, long long> sal[N];
bool solve(long long m, long long to, long long n) {
  long long sum = 0;
  int cnt = 0, rem, i;
  vector<long long> ss;
  for (i = 0; i < n; i++) {
    if (sal[i].second < m)
      sum += sal[i].first;
    else if (sal[i].first >= m)
      sum += sal[i].first, cnt++;
    else
      ss.push_back(sal[i].first);
  }
  rem = max(0LL, ((n + 1) / 2) - cnt);
  if (rem > ss.size()) return false;
  for (i = ss.size() - 1; i > -1; i--) {
    if (rem > 0)
      sum += m, rem--;
    else
      sum += ss[i];
  }
  return (sum <= to ? true : false);
}
int main() {
  long long t, n, i, lo, hi, to, mid;
  scanf("%lld", &t);
  while (t--) {
    scanf("%lld %lld", &n, &to);
    for (i = 0; i < n; i++) scanf("%lld %lld", &sal[i].first, &sal[i].second);
    sort(sal, sal + n);
    lo = 1, hi = to;
    while (lo <= hi) {
      mid = (lo + hi) / 2;
      if (solve(mid, to, n))
        lo = mid + 1;
      else
        hi = mid - 1;
    }
    printf("%lld\n", lo - 1);
  }
  return 0;
}
