#include <bits/stdc++.h>
using namespace std;
const long long N = 200010;
pair<long long, long long> a[N];
long long n;
long long s;
vector<long long> v;
bool check(long long k) {
  long long ls = 0, rs = 0;
  long long sum = 0;
  v.clear();
  for (long long i = 1; i <= n; ++i) {
    if (a[i].second < k)
      ls++, sum += a[i].first;
    else if (a[i].first > k)
      rs++, sum += a[i].first;
    else
      v.push_back(a[i].first);
  }
  if (sum > s || ls > n / 2 || rs > n / 2) return false;
  sort(v.begin(), v.end());
  for (auto t : v) {
    if (ls == n / 2) break;
    sum += t;
    ls++;
  }
  sum += (n / 2 + 1 - rs) * k;
  return sum <= s;
}
signed main() {
  long long T;
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld%lld", &n, &s);
    for (long long i = 1; i <= n; ++i)
      scanf("%lld%lld", &a[i].first, &a[i].second);
    sort(a + 1, a + 1 + n);
    long long l = a[n / 2].first, r = 2e14, ans;
    while (l <= r) {
      long long mid = (l + r) / 2;
      if (check(mid)) {
        l = mid + 1;
        ans = mid;
      } else
        r = mid - 1;
    }
    cout << ans << endl;
  }
  return 0;
}
