#include <bits/stdc++.h>   using namespace std;   const double eps = 1e-6;   const int mod = 1e9 + 7;   const int maxn = 2e6 + 100;   const int maxm = 2e6 + 100;   const int inf = 0x3f3f3f3f;   const double pi = acos(-1.0);   int t;   pair<long long, long long> a[maxn];   long long s;   int n;   int vis[maxn];   bool cmp2(pair<long long, long long> a, pair<long long, long long> b) {     return a.second < b.second;   }   vector<long long> mm, rr, lll;   int ck(long long x) {     int L = 0, R = 0, M = 0;     lll.clear();     rr.clear();     mm.clear();     for (int i = 1; i <= n; i++) {       if (a[i].first <= x && a[i].second >= x) {         mm.push_back(a[i].first);         M++;         continue;       }       if (a[i].first > x) {         R++;         rr.push_back(a[i].first);       }       if (a[i].second < x) {         L++;         lll.push_back(a[i].first);       }     }     if (L > n / 2) return false;     long long res = 0;     sort(mm.begin(), mm.end());     if (L < n / 2) {       int to = M;       for (int i = 0; i < to; i++) {         lll.push_back(mm[i]);         L++;         M--;         if (L == n / 2) break;       }     }     if (R < n / 2 + 1) {       if (R + M != n / 2 + 1) return false;       res += 1ll * M * x;     }     for (int i = 0; i < (int)lll.size(); i++) {       res += lll[i];     }     for (int i = 0; i < (int)rr.size(); i++) {       res += max(rr[i], x);     }     return res <= s;   }   int main() {     scanf( %d , &t);     while (t--) {       long long mx = 0;       scanf( %d %lld , &n, &s);       for (int i = 1; i <= n; i++) {         scanf( %lld %lld , &a[i].first, &a[i].second);         mx = max(mx, a[i].second);       }       long long ans = 0;       sort(a + 1, a + 1 + n);       long long l = a[n / 2 + 1].first;       sort(a + 1, a + 1 + n, cmp2);       long long r = a[n / 2 + 1].second;       while (l <= r) {         long long mid = l + r >> 1;         if (ck(mid)) {           l = mid + 1;           ans = mid;         } else           r = mid - 1;       }       printf( %lld n , ans);     }     return 0;   }   