#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int t, n;
long long s, sum;
pair<int, int> opt[maxn];
bool check(int mid) {
  int k = 0;
  long long total = sum;
  for (int i = n; i >= 1; --i) {
    if (opt[i].second >= mid) {
      k++;
      if (mid >= opt[i].first) total += mid - opt[i].first;
      if (k == (n + 1) / 2) break;
    }
  }
  return k == (n + 1) / 2 && total <= s;
}
int main() {
  scanf("%d", &t);
  while (t--) {
    sum = 0;
    scanf("%d%lld", &n, &s);
    int L, R;
    for (int i = 1; i <= n; ++i) {
      int l, r;
      scanf("%d%d", &l, &r);
      opt[i] = {l, r};
      L = min(L, l);
      R = max(R, r);
      sum += l;
    }
    sort(opt + 1, opt + 1 + n);
    while (L < R) {
      int mid = (L + R + 1) >> 1;
      if (check(mid))
        L = mid;
      else
        R = mid - 1;
    }
    printf("%d\n", L);
  }
  return 0;
}
