#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int t, n;
long long s;
struct uzi {
  int l, r;
  bool operator<(const uzi& t) const { return l > t.l; }
} p[N];
int vis[N];
int main() {
  ios::sync_with_stdio(false);
  for (cin >> t; t; t--) {
    cin >> n >> s;
    long long S = 0;
    for (int i = 1; i <= n; i++) cin >> p[i].l >> p[i].r, S += p[i].l;
    sort(p + 1, p + 1 + n);
    int l = p[n / 2 + 1].l, r = 1e9, ans = 0;
    while (l <= r) {
      int mid = l + r >> 1;
      long long sum = 0;
      int sz = 0;
      long long tmp = S;
      for (int i = 1; i <= n; i++) {
        if (p[i].l > mid) {
          sz++;
          sum += p[i].l;
          vis[i] = 1;
          tmp -= p[i].l;
        }
      }
      int tot = 0;
      for (int i = 1; i <= n; i++) {
        if (p[i].l <= mid && p[i].r >= mid && sz <= n / 2) {
          vis[i]++;
          sz++;
          tot++;
          sum += mid;
          tmp -= p[i].l;
        }
      }
      if (sz <= n / 2)
        r = mid - 1;
      else {
        sum += tmp;
        if (sum <= s)
          ans = mid, l = mid + 1;
        else
          r = mid - 1;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}
