#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e9 + 200ll;
bool can(vector<pair<int, int>> a, long long tar, int n, long long s) {
  int cnt = 0;
  long long sum = 0ll;
  vector<int> use;
  for (int i = 0; i < n; ++i) {
    if (a[i].second < tar) {
      sum += (long long)a[i].first;
    } else if (a[i].first >= tar) {
      sum += (long long)a[i].first;
      cnt++;
    } else {
      use.push_back(a[i].first);
    }
  }
  int want = max(0, (n + 1) / 2 - cnt);
  if (want > use.size()) return false;
  for (int i = 0; i < use.size(); ++i) {
    if (i < use.size() - want) {
      sum += (long long)use[i];
    } else {
      sum += tar;
    }
  }
  return sum <= s;
}
int main() {
  ios::sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    long long s;
    cin >> n >> s;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());
    long long ans = 0ll;
    long long l = 0ll, r = INF;
    while (l <= r) {
      long long mid = (l + r) / 2ll;
      if (can(a, mid, n, s)) {
        l = mid + 1ll;
        ans = mid;
      } else {
        r = mid - 1ll;
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
