#include <bits/stdc++.h>
using namespace std;
long long mo(const long long input, const long long ceil) {
  return input >= ceil ? input % ceil : input;
}
long long n, s, ans, l, r, i, mid, cnt, sum;
pair<long long, long long> a[400000];
void solve(long long tt) {
  cin >> n >> s;
  for (i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second;
  }
  sort(a + 1, a + n + 1);
  ans = 1, l = 1, r = 1000000000000000;
  while (l <= r) {
    mid = (l + r) / 2;
    cnt = (n + 1) / 2;
    sum = 0;
    for (i = n; i >= 1; i--) {
      if (a[i].second >= mid && cnt) {
        sum = sum + max(a[i].first, mid);
        cnt--;
      } else
        sum = sum + a[i].first;
    }
    if (sum <= s && cnt == 0) {
      l = mid + 1;
      ans = mid;
    } else
      r = mid - 1;
  }
  cout << ans << "\n";
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long tt = 1;
  cin >> tt;
  for (long long i = 0; i < tt; i++) solve(tt);
  cerr << "\n\n\nTime : "
       << 1000 * (long double)clock() / (long double)CLOCKS_PER_SEC << "ms\n";
  ;
  return 0;
}
