#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
long long tot;
int n;
pair<int, int> a[maxn];
bool judge(int mid) {
  long long sum = 0;
  int cnt = 0;
  vector<int> v;
  for (int i = 0; i < n; i++) {
    if (a[i].second < mid)
      sum += a[i].first;
    else if (a[i].first >= mid) {
      sum += a[i].first;
      cnt++;
    } else
      v.push_back(a[i].first);
  }
  sort(v.begin(), v.end());
  cnt = max(0, (n + 1) / 2 - cnt);
  if (cnt > v.size()) return 0;
  for (int i = 0; i < v.size(); i++) {
    if (i < v.size() - cnt)
      sum += v[i];
    else
      sum += mid;
  }
  return sum <= tot;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%lld", &n, &tot);
    for (int i = 0; i < n; i++) {
      scanf("%d%d", &a[i].first, &a[i].second);
    }
    sort(a, a + n);
    int l = 1, r = 1e9 + 10;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (judge(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    printf("%d\n", l);
  }
  return 0;
}
