#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
signed main(void) {
  long long q;
  cin >> q;
  for (long long(fjfea) = 0; (fjfea) < (q); (fjfea)++) {
    long long n, money;
    cin >> n >> money;
    vector<pair<long long, long long>> range(n);
    for (long long(i) = 0; (i) < (n); (i)++) {
      long long a, b;
      cin >> a >> b;
      range[i] = make_pair(a, b);
    }
    sort(range.begin(), range.end());
    long long l = -1, r = money * 2;
    bool paid[n];
    while (abs(r - l) > 1) {
      long long cost = 0, low = 0, high = 0;
      memset(paid, false, n);
      long long mid = (r + l) / 2;
      for (long long(i) = 0; (i) < (n); (i)++) {
        if (range[i].second < mid)
          cost += range[i].first, low++, paid[i] = true;
        if (range[i].first > mid)
          cost += range[i].first, high++, paid[i] = true;
      }
      if (low > n / 2 || cost > money) {
        r = mid;
        continue;
      }
      if (high > n / 2) {
        l = mid;
        continue;
      }
      for (long long(i) = 0; (i) < (n); (i)++) {
        if (!paid[i]) {
          if (low < n / 2) {
            low++;
            cost += range[i].first;
            paid[i] = true;
          } else {
            cost += mid;
            high++;
          }
        }
      }
      if (cost > money) {
        r = mid;
        continue;
      } else
        l = mid;
    }
    cout << l << endl;
  }
}
