#include <bits/stdc++.h>
using namespace std;
int t, n;
long long s;
struct node {
  long long l, r;
} nod[200005];
vector<long long> ve;
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d%lld", &n, &s);
    for (int i = 1; i <= n; ++i) scanf("%lld%lld", &nod[i].l, &nod[i].r);
    long long l = 1, r = s, mid, ans;
    while (l <= r) {
      mid = (l + r) >> 1;
      int cntl = 0, cntr = 0;
      long long cos = 0;
      ve.clear();
      for (int i = 1; i <= n; ++i) {
        if (nod[i].r < mid)
          cos += nod[i].l, ++cntr;
        else if (nod[i].l > mid)
          cos += nod[i].l, ++cntl;
        else
          ve.push_back(nod[i].l);
      }
      if (cntl >= (n + 1) / 2)
        ans = mid, l = mid + 1;
      else if (cntr > n / 2)
        r = mid - 1;
      else {
        sort(ve.begin(), ve.end());
        int k = n / 2 - cntr;
        for (int i = 0; i < k; ++i) cos += ve[i];
        cos += (ve.size() - k) * mid;
        if (cos <= s) {
          l = mid + 1;
          ans = mid;
        } else
          r = mid - 1;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}
