#include <bits/stdc++.h>
using namespace std;
template <class T>
int read(T& x) {
  int c = getchar(), f = (x = 0);
  while (~c && (c < 48 || c > 57)) {
    if (c == '-') {
      f = 1;
    }
    c = getchar();
  }
  if (!~c) {
    return 0;
  }
  while (c > 47 && c < 58) {
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  }
  if (f) {
    x = -x;
  }
  return 1;
}
template <class T, class U>
inline int read(T& a, U& b) {
  return read(a) && read(b);
}
template <class T, class U, class V>
inline int read(T& a, U& b, V& c) {
  return read(a) && read(b) && read(c);
}
inline int read(double& _, double& __) { return scanf("%lf%lf", &_, &__); }
inline int read(char* _) { return scanf("%s", _); }
inline int read(double& _) { return scanf("%lf", &_); }
inline void print(long long _) { printf("%lld ", _); }
inline void print(int _) { printf("%d ", _); }
inline void println(long long _) { printf("%lld\n", _); }
inline void println(int _) { printf("%d\n", _); }
template <class T>
inline void cmax(T& _, T __) {
  if (_ < __) _ = __;
}
template <class T>
inline void cmin(T& _, T __) {
  if (_ > __) _ = __;
}
const int maxn = 2e5 + 10, INF = 0x3f3f3f3f;
const long long LINF = (long long)INF << 32 | INF;
long long mid;
struct Node {
  long long L, R;
  Node(long long a = 0, long long b = 0) : L(a), R(b) {}
  bool operator<(const Node& T) const { return L > T.L; }
} a[maxn];
long long T, n, tot, L = 0, R = INF, x;
bool Judge() {
  int cnt = 0;
  long long tmp = tot;
  for (int i = 1; i <= (n); i++) {
    if (a[i].L >= mid) {
      ++cnt;
      continue;
    }
    if (a[i].R < mid) continue;
    if (tmp < mid - a[i].L) break;
    tmp -= mid - a[i].L;
    if (++cnt >= x) return true;
  }
  return cnt >= x;
}
int main() {
  int T;
  read(T);
  while (T--) {
    read(n, tot);
    L = 0, R = tot, x = (n + 1) / 2;
    for (int i = 1; i <= (n); i++) {
      read(a[i].L, a[i].R);
      tot -= a[i].L;
    }
    sort(a + 1, a + n + 1);
    while (L < R) {
      mid = L + (R - L + 1) / 2;
      if (Judge())
        L = mid;
      else
        R = mid - 1;
    }
    printf("%lld\n", L);
  }
  return 0;
}
