#include <bits/stdc++.h>
using namespace std;
long long s;
int n;
vector<pair<int, int>> lims;
int solve(int median) {
  int smallcnt = 0;
  int largecnt = 0;
  long long rem = s;
  for (int i = 0; i < n; i++)
    if (lims[i].second < median) {
      smallcnt++;
      rem -= lims[i].first;
    } else if (lims[i].first > median) {
      largecnt++;
      rem -= lims[i].first;
    }
  if (largecnt > n / 2) return -1;
  if (smallcnt > n / 2) return 1;
  int smallleft = n / 2 - smallcnt;
  for (int i = 0; i < n && smallleft > 0; i++)
    if (lims[i].first <= median && lims[i].second >= median) {
      rem -= lims[i].first;
      smallleft--;
    }
  int stillneed = n - n / 2 - largecnt;
  if (1LL * stillneed * median > rem) return 1;
  return 0;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> s;
    lims.resize(n);
    for (int i = 0; i < n; i++) cin >> lims[i].first >> lims[i].second;
    sort(lims.begin(), lims.end());
    int low = 1, high = 1000000000;
    while (low < high) {
      int mid = (low + high) >> 1;
      if (mid == low) mid++;
      int res = solve(mid);
      if (res == 1)
        high = mid - 1;
      else if (res == -1)
        low = mid + 1;
      else
        low = mid;
    }
    cout << low << "\n";
  }
  return 0;
}
