#include <bits/stdc++.h>
using namespace std;
int main() {
  int t, n, i;
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> t;
  while (t--) {
    long long s;
    cin >> n >> s;
    vector<int> l(n), r(n);
    for (i = 0; i < n; i++) {
      cin >> l[i] >> r[i];
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(),
         [&](const int &x, const int &y) { return l[x] > l[y]; });
    auto check = [&](long long lim) -> bool {
      long long sum = 0;
      int cnt = 0;
      for (auto it : ord) {
        sum += l[it];
        long long cur = max(0LL, lim - l[it]);
        if (r[it] >= lim && cnt < (n + 1) / 2) {
          sum += cur;
          cnt++;
        }
        if (sum > s) return 0;
      }
      return ((cnt == (n + 1) / 2) && sum <= s);
    };
    long long res = 0;
    for (long long step = 1LL << 50; step; step >>= 1) {
      if (check(res + step)) {
        res += step;
      }
    }
    cout << res << "\n";
  }
  return 0;
}
