#include <bits/stdc++.h>
using namespace std;
long long t, n, S, s, up, down, mid, mx, mn, a, b, k, l, r, ans, raod;
pair<long long, long long> p[300005];
int main() {
  cin >> t;
  while (t--) {
    cin >> n >> S;
    mn = 1e10;
    mx = 0;
    for (k = 1; k <= n; k++) {
      cin >> a >> b;
      p[k].first = a;
      mn = min(mn, a);
      p[k].second = b;
      mx = max(mx, b);
    }
    ans = 0;
    sort(p + 1, p + n + 1);
    l = mn;
    r = mx;
    while (l <= r) {
      long long mid = (l + r + 1) / 2;
      up = 0;
      down = 0;
      s = 0;
      for (k = 1; k <= n; k++)
        if (p[k].first > mid)
          up++;
        else if (p[k].second < mid)
          down++;
      if (up >= n / 2 + 1) {
        l = mid + 1;
      } else if (down >= n / 2 + 1)
        r = mid - 1;
      else {
        raod = 0;
        for (k = n; k >= 1; k--) {
          if (raod <= n / 2 & p[k].second >= mid) {
            raod++;
            s += max(mid, p[k].first);
          } else
            s += p[k].first;
        }
        if (s <= S) {
          ans = mid;
          l = mid + 1;
        } else
          r = mid - 1;
      }
    }
    cout << ans << endl;
  }
}
