#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
struct Node {
  long long l, r;
} dict[maxn];
long long N, s;
inline bool check(long long mid) {
  long long cnt = 0, cost = 0;
  priority_queue<long long, vector<long long>, greater<long long>> q;
  for (int i = 1; i <= N; ++i) {
    cost += dict[i].l;
    if (dict[i].l < mid && dict[i].r >= mid) {
      q.push(mid - dict[i].l);
    } else if (dict[i].l >= mid) {
      ++cnt;
    }
  }
  while (!q.empty() && cnt < (N + 1) / 2) {
    cost += q.top();
    q.pop();
    cnt++;
  }
  return cost <= s && cnt >= (N + 1) / 2;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld", &N, &s);
    for (int i = 1; i <= N; ++i) {
      scanf("%lld%lld", &dict[i].l, &dict[i].r);
    }
    long long l = 1, r = 1e14, ans;
    while (l <= r) {
      long long mid = (l + r) >> 1;
      if (check(mid))
        ans = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    cout << ans << endl;
  }
  return 0;
}
