#include <bits/stdc++.h>
using namespace std;
const long long mx = 200005;
bool comparator(pair<long long, long long> A, pair<long long, long long> B) {
  return A.first < B.first;
}
int main() {
  ios::sync_with_stdio(0);
  long long q;
  cin >> q;
  while (q--) {
    long long n, s;
    long long l;
    long long r;
    long long ans = 0;
    vector<pair<long long, long long>> intv, Min, Max;
    cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
      int l, r;
      cin >> l >> r;
      intv.push_back(make_pair(l, r));
      Min.push_back(make_pair(l, i - 1));
      Max.push_back(make_pair(r, i - 1));
    }
    sort(Min.begin(), Min.end(), comparator);
    sort(Max.begin(), Max.end(), comparator);
    l = Min[n / 2].first;
    r = Max[n / 2].first;
    while (l <= r) {
      long long m = (l + r) / 2;
      long long cost = m;
      long long cntLeft = 0;
      long long cntRight = 0;
      vector<pair<int, int>> both;
      for (int i = 0; i < n; ++i) {
        if (intv[i].second < m)
          cost += intv[i].first, ++cntLeft;
        else if (intv[i].first > m)
          cost += intv[i].first, ++cntRight;
        else if (intv[i].first <= m && intv[i].second >= m)
          both.push_back(intv[i]);
      }
      sort(both.begin(), both.end(), comparator);
      for (int i = 0; i < both.size() && cntLeft < n / 2; ++i)
        cost += both[i].first, ++cntLeft;
      for (int i = both.size() - 1; i >= 0 && cntRight < n / 2; --i)
        cost += m, ++cntRight;
      if (cost <= s) {
        ans = max(ans, m);
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
