#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const double PI = acos(-1);
long long mod = 1e9 + 7;
struct segment {
  long long l, r;
  bool operator<(const segment& s) const { return l < s.l; }
};
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n, s;
    cin >> n >> s;
    vector<segment> vs(n);
    for (long long i = 0; i < n; i++) cin >> vs[i].l >> vs[i].r;
    long long low = 1, high = s + 1;
    while (low < high) {
      long long mid = (low + high + 1) / 2;
      vector<segment> tmp;
      long long cost = 0, left = 0, right = 0;
      for (long long i = 0; i < n; i++) {
        if (vs[i].r < mid) {
          left++;
          cost += vs[i].l;
        } else if (vs[i].l > mid) {
          right++;
          cost += vs[i].l;
        } else
          tmp.push_back(vs[i]);
      }
      sort(tmp.begin(), tmp.end());
      long long rem = n / 2 - left;
      for (long long i = 0; i < tmp.size(); i++) {
        if (rem > 0) {
          rem--;
          cost += tmp[i].l;
          left++;
        } else {
          cost += mid;
          right++;
        }
      }
      if (cost > s || left >= right)
        high = mid - 1;
      else
        low = mid;
    }
    cout << low << "\n";
  }
  return 0;
}
