#include <bits/stdc++.h>
using namespace std;
int amount;
long long total;
pair<int, int> salary[1000005];
bool is_good(int median_sal) {
  int need = (amount + 1) / 2;
  long long total_need = 0;
  for (int i = amount; i >= 1; i--)
    if (salary[i].first >= median_sal) {
      need--;
      total_need += salary[i].first;
    } else
      break;
  for (int i = amount; i >= 1; i--)
    if (salary[i].first < median_sal) {
      if (need > 0 && salary[i].second >= median_sal)
        need--, total_need += median_sal;
      else
        total_need += salary[i].first;
    }
  return (total_need <= total && need <= 0);
}
void solve() {
  scanf("%d %lld", &amount, &total);
  for (int i = 1; i <= amount; i++)
    scanf("%d %d", &salary[i].first, &salary[i].second);
  sort(salary + 1, salary + amount + 1);
  int head = (int)1e9 + 5, tail = 0;
  while (head - tail > 1) {
    int mid = (head + tail) >> 1;
    if (is_good(mid))
      tail = mid;
    else
      head = mid;
  }
  printf("%d\n", tail);
}
int main() {
  int tester;
  scanf("%d", &tester);
  while (tester--) solve();
}
