#include <bits/stdc++.h>
using namespace std;
long long n, second;
long long minS = 0;
vector<int> ptats;
vector<pair<int, int>> lr;
bool check(long long median) {
  long long excess = 0;
  int it = upper_bound(ptats.begin(), ptats.end(), median) - ptats.begin() - 1;
  int left = it;
  int right = (n - it - 1);
  if (left < right) {
    return false;
  }
  int cnt = (left - right) / 2 + 1;
  for (int i = it; i >= 0 && cnt; i--) {
    if (lr[i].second >= median) {
      excess += (median - lr[i].first);
      cnt--;
    }
  }
  return excess + minS <= second && cnt == 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    ptats.clear();
    lr.clear();
    minS = 0;
    cin >> n >> second;
    for (int i = 0; i < n; i++) {
      int x, y;
      cin >> x >> y;
      lr.push_back({x, y});
      minS += x;
    }
    ptats.resize(n);
    sort(lr.begin(), lr.end());
    for (int i = 0; i < n; i++) {
      ptats[i] = lr[i].first;
    }
    int l = lr[n / 2].first;
    long long r = 1e15;
    while (l < r) {
      long long mid = l + (r - l + 1) / 2;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    cout << l << "\n";
  }
  return 0;
}
