#include <bits/stdc++.h>
using namespace std;
template <class T>
bool umin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool umax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
long long POW(long long a, long long p, long long M) {
  if (!p) return 1LL;
  long long T = POW(a, p / 2, M);
  T = T * T % M;
  if (p & 1) T = T * (a % M) % M;
  return T;
}
long long SQRT(long long a) {
  long long b = (long long)sqrtl(((double)a) + 0.5);
  while (b * b < a) ++b;
  while (b * b > a) --b;
  return (b * b == a) ? b : -1;
}
const long long MOD = 1e9 + 7;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  int q;
  cin >> q;
  while (q--) {
    int n;
    cin >> n;
    long long s;
    cin >> s;
    vector<pair<long long, long long>> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    sort((v).begin(), (v).end());
    long long L = v[n / 2].first;
    long long R = 1e15;
    long long ff = L;
    while (L <= R) {
      long long mid = L + R;
      mid /= 2;
      long long f = 0;
      int ct = 0;
      bool ps = false;
      vector<long long> tt;
      for (auto i : v) {
        if (i.first > mid) {
          f += i.first;
          ct++;
        } else if (i.second < mid)
          f += i.first;
        else
          tt.push_back(i.first);
      }
      if (tt.size()) {
        ct++;
        ps = true;
        f += mid;
        tt.pop_back();
      }
      while (ct < (n + 1) / 2 && tt.size()) {
        ct++;
        f += mid;
        tt.pop_back();
      }
      for (auto i : tt) f += i;
      if (f <= s && ps && ct == (n + 1) / 2) {
        L = mid + 1;
        ff = mid;
      } else
        R = mid - 1;
    }
    cout << ff << endl;
  }
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";
  return 0;
}
