#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
bool possible(long long val, long long s, vector<pair<int, int>> &pl, int n) {
  long long tot = 0, cnt = (n + 1) / 2;
  vector<int> llp;
  for (int i = 0; i < n; i++) {
    if (pl[i].first >= val) {
      tot += pl[i].first;
      cnt--;
    } else if (pl[i].second < val) {
      tot += pl[i].first;
    } else {
      llp.push_back(pl[i].first);
    }
  }
  if (cnt <= 0) return true;
  if (cnt > llp.size()) return false;
  sort(llp.begin(), llp.end());
  for (int i = 0; i < llp.size() - cnt; i++) {
    tot += llp[i];
  }
  tot += val * cnt;
  return tot <= s;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    long long s;
    cin >> n >> s;
    long long high, low;
    vector<pair<int, int>> pl(n);
    for (int i = 0; i < n; i++) {
      cin >> pl[i].first >> pl[i].second;
    }
    if (n == 1) {
      cout << min(s, (long long)pl[0].second) << endl;
      continue;
    }
    low = 0;
    high = s;
    while (low + 1 < high) {
      long long mid = (low + high) / 2;
      if (possible(mid, s, pl, n)) {
        low = mid;
      } else {
        high = mid;
      }
    }
    cout << low << endl;
  }
  return 0;
}
