#include <bits/stdc++.h>
using namespace std;
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int n;
    long long s;
    scanf("%d %I64d", &n, &s);
    long long deb = 0, fin = s;
    int l[n], r[n];
    for (int i = 0; i < n; i++) {
      scanf("%d %d", &l[i], &r[i]);
      s -= l[i];
    }
    while (deb < fin) {
      long long mid = (deb + fin + 1) / 2;
      priority_queue<int> suiv;
      for (int i = 0; i < n; i++) {
        if (r[i] >= mid) suiv.push(l[i]);
      }
      if ((int)suiv.size() < (n + 1) / 2) {
        fin = mid - 1;
        continue;
      }
      long long spend = 0;
      for (int i = 0; i < (n + 1) / 2; i++) {
        spend += max(0ll, mid - suiv.top());
        suiv.pop();
      }
      if (spend <= s)
        deb = mid;
      else
        fin = mid - 1;
    }
    printf("%I64d\n", deb);
  }
  return 0;
}
