#include <bits/stdc++.h>
using namespace std;
long long int a[200010][2];
bool check(long long int m, long long int n, long long int s) {
  long long int aa = 0, bb = 0;
  long long int sal = 0;
  vector<pair<int, int>> v;
  for (int i = 0; i < n; i++) {
    if (a[i][1] < m)
      aa++, sal = sal + a[i][0];
    else if (a[i][0] >= m)
      bb++, sal = sal + a[i][0];
    else
      v.push_back({a[i][0], a[i][1]});
  }
  long long int p = (n / 2) - aa;
  long long int q = (n / 2) + 1 - bb;
  if (bb >= ((n / 2) + 1)) {
    for (long long int i = 0; i < v.size(); i++) sal = sal + v[i].first;
    if (sal <= s)
      return true;
    else
      return false;
  } else if (p >= 0 && q >= 0) {
    sort(v.begin(), v.end());
    for (int i = 0; i < p; i++) sal = sal + v[i].first;
    sal = sal + (q * m);
    if (sal <= s)
      return true;
    else
      return false;
  } else
    return false;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    long long int n, s;
    cin >> n >> s;
    long long int l = INT_MAX, r = 0;
    for (int i = 0; i < n; i++) {
      cin >> a[i][0] >> a[i][1];
      r = max(r, a[i][1]);
      l = min(l, a[i][0]);
    }
    long long int ans = 0;
    while (l <= r) {
      long long int m = (l + r) / 2;
      if (check(m, n, s))
        ans = m, l = m + 1;
      else
        r = m - 1;
    }
    cout << ans << endl;
  }
  return 0;
}
