#include <bits/stdc++.h>
const double PI = 3.141592653589793238460;
using namespace std;
pair<long long int, long long int> ar[200001];
bool isPossible(long long int mid, long long int s, long long int n) {
  long long int sum = 0;
  int cnt = 0;
  vector<int> va, vb, vc;
  for (int i = 1; i <= n; i++) {
    if (ar[i].second < mid)
      va.push_back(i), sum += ar[i].first;
    else if (ar[i].first > mid)
      vb.push_back(i), sum += ar[i].first, cnt++;
    else
      vc.push_back(i);
  }
  int rem = max((long long int)0, n / 2 + 1 - cnt);
  if (rem > vc.size()) return false;
  while (vc.size() > 0) {
    if (rem)
      sum += mid, rem--;
    else
      sum += ar[vc.back()].first;
    vc.pop_back();
  }
  return sum <= s;
}
long long int getAns(long long int n, long long int s) {
  long long int L = ar[1].first;
  long long int H = 1000000000;
  long long int res = 1;
  while (L <= H) {
    long long int mid = (L + H) / 2;
    if (isPossible(mid, s, n))
      res = max(res, mid), L = mid + 1;
    else
      H = mid - 1;
  }
  return res;
}
bool comp(pair<long long int, long long int> a,
          pair<long long int, long long int> b) {
  return a.first < b.first;
}
int main() {
  long long int t, n, s;
  cin >> t;
  while (t--) {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) cin >> ar[i].first >> ar[i].second;
    sort(ar + 1, ar + n + 1, comp);
    cout << getAns(n, s) << '\n';
  }
}
