#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int t, n;
long long s;
pair<int, int> x[N];
bool valid(int mid) {
  int cnt = (n + 1) / 2;
  long long sum = s;
  for (int i = n - 1; ~i; --i) {
    if (cnt && mid <= x[i].second)
      --cnt, sum -= max(x[i].first, mid);
    else
      sum -= x[i].first;
  }
  return sum >= 0 && !cnt;
}
int solve() {
  int l = 0, r = 1e9 + 5;
  while (l < r) {
    int mid = l + (r - l + 1) / 2;
    if (valid(mid))
      l = mid;
    else
      r = mid - 1;
  }
  return l;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  while (t--) {
    cin >> n >> s;
    for (int i = 0; i < n; ++i) cin >> x[i].first >> x[i].second;
    sort(x, x + n, [](pair<int, int>& a, pair<int, int>& b) {
      return a.first < b.first;
    });
    cout << solve() << '\n';
  }
  return 0;
}
