#include <bits/stdc++.h>
using namespace std;
const double pai = acos(-1);
const double eps = 1e-10;
const long long mod = 1e9 + 7;
const int MXN = 1e6 + 5;
long long a[MXN], b[MXN];
int vis[MXN];
int n;
long long s;
struct no {
  long long l, r, p;
};
bool operator<(const no &x, const no &y) { return x.l > y.l; }
bool check(long long mid) {
  vector<no> v;
  for (int i = 1; i <= n; i++) {
    if (b[i] >= mid) v.push_back(no{a[i], b[i], i});
    vis[i] = 0;
  }
  if ((int)v.size() < n / 2 + 1) return 0;
  sort(v.begin(), v.end());
  while ((int)v.size() > n / 2 + 1) v.pop_back();
  long long need = 0;
  for (auto i : v) need += max(mid, i.l), vis[i.p] = 1;
  for (int i = 1; i <= n; i++)
    if (!vis[i]) need += a[i];
  return need <= s;
}
void Main(int avg) {
  cin >> n >> s;
  for (int i = 1; i <= n; i++) {
    int sa, sb;
    scanf("%d %d", &sa, &sb);
    a[i] = sa, b[i] = sb;
  }
  long long l = 1, r = 1e9, ans;
  while (l <= r) {
    long long mid = (l + r) / 2;
    if (check(mid))
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  cout << ans << '\n';
}
int main() {
  int cas;
  cin >> cas;
  for (int i = 1; i <= cas; i++) Main(i);
  return 0;
}
