#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;   }   