#include <bits/stdc++.h>
using namespace std;
long long add(long long a, long long b, long long mod) {
  return (a % mod + b % mod) % mod;
}
long long sub(long long a, long long b, long long mod) {
  return (a % mod - b % mod + mod) % mod;
}
long long mul(long long a, long long b, long long mod) {
  return ((a % mod) * (b % mod)) % mod;
}
long long sumodd(long long num, long long mod) { return mul(num, num, mod); }
long long sumeven(long long num, long long mod) {
  return mul(num, num + 1, mod);
}
long long sum_any_range(long long st, long long en, long long num) {
  return (num * (st + en) / 2);
}
long long gcd(long long a, long long b) {
  while (b != 0) {
    long long a2 = a;
    a = b;
    b = a2 % b;
  }
  return a;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
string makeitbinary(long long n) {
  string s;
  while (n) {
    s = s + (char)((n % 2) + '0');
    n /= 2;
  }
  reverse(s.begin(), s.end());
  return s;
}
bool bit(int num, int i) { return ((num >> i) & 1); }
long long fastpowermod(long long b, long long p, long long mod) {
  long long ans = 1;
  while (p) {
    if (p % 2) {
      ans = mul(ans, b, mod);
    }
    b = mul(b, b, mod);
    p /= 2;
  }
  return ans;
}
long long fastpower(long long b, long long p) {
  long long ans = 1;
  while (p) {
    if (p % 2) {
      ans = ans * b;
    }
    b = b * b;
    p /= 2;
  }
  return ans;
}
double fastpower_double(double b, long long p) {
  double ans = 1;
  while (p) {
    if (p % 2) {
      ans = ans * b;
    }
    b = b * b;
    p /= 2;
  }
  return ans;
}
long long summation_formula(long long n) { return (n * (n + 1) / 2); }
bool lower_vowel(char c) {
  return (c == 'i' || c == 'o' || c == 'u' || c == 'a' || c == 'e');
}
string bigint_mini(string s1, string s2) {
  if (s1.size() > s2.size()) {
    return s2;
  } else if (s2.size() > s1.size()) {
    return s1;
  }
  for (int i = 0; i < s1.size(); i++) {
    if ((s1[i] - '0') > (s2[i] - '0')) {
      return s2;
    } else if ((s2[i] - '0') > (s1[i] - '0')) {
      return s1;
    }
  }
  return s1;
}
double polygon_area(int n, vector<double> X, vector<double> Y) {
  double area = 0.0;
  int j = n - 1;
  for (int i = 0; i < n; i++) {
    area += (X[j] + X[i]) * (Y[j] - Y[i]);
    j = i;
  }
  return abs(area / 2.0);
}
long long sum_of_digits(string s) {
  long long sum = 0;
  for (int i = 0; i < s.size(); i++) {
    sum += s[i] - '0';
  }
  return sum;
}
string makeitbase(long long num, long long base) {
  string s;
  while (num) {
    long long mod = num % base;
    s += (mod + '0');
    num /= base;
  }
  reverse(s.begin(), s.end());
  return s;
}
bool intersect(long long l1, long long r1, long long l2, long long r2) {
  return (max(l1, l2) <= min(r1, r2));
}
pair<long long, long long> find_intersection(long long l1, long long r1,
                                             long long l2, long long r2) {
  return {max(l1, l2), min(r1, r2)};
}
long long sum_ranges(long long l, long long r) {
  return summation_formula(r) - summation_formula(l);
}
double power_2(double num) { return num * num; }
bool isPowerOfTwo(int x) { return (x && !(x & (x - 1))); }
long long modInverse(long long A, long long M) {
  return fastpowermod(A, M - 2, M);
}
long long num_inrange(long long l, long long r) {
  l = min(l, r);
  r = max(l, r);
  return r - l + 1;
}
long long how_many_factor(long long num, long long t) {
  long long cnt = 0;
  while (num != 0 && num % t == 0) {
    num /= t;
    cnt++;
  }
  return cnt;
}
pair<pair<long long, long long>, pair<long long, long long> >
formula_rotate_left_(long long x, long long y, long long row_len,
                     long long col_len) {
  long long nx = col_len - y - 1;
  long long ny = x;
  return {{nx, ny}, {col_len, row_len}};
}
pair<pair<long long, long long>, pair<long long, long long> >
formula_rotate_right_(long long x, long long y, long long row_len,
                      long long col_len) {
  long long nx = y;
  long long ny = row_len - x - 1;
  return {{nx, ny}, {col_len, row_len}};
}
pair<pair<long long, long long>, pair<long long, long long> > horizontal_rotate(
    long long x, long long y, long long row_len, long long col_len) {
  long long nx = x;
  long long ny = col_len - y - 1;
  return {{nx, ny}, {row_len, col_len}};
}
long long mod_big_integer(string s, long long M) {
  long long num = 0;
  for (long long i = 0; i < s.size(); i++) {
    num = add(mul(num, 10, M), (s[i] - '0'), M);
  }
  return num;
}
struct Point {
  long long x, y;
};
long long overlappingArea(Point l1, Point r1, Point l2, Point r2) {
  long long area1 = abs(l1.x - r1.x) * abs(l1.y - r1.y);
  long long area2 = abs(l2.x - r2.x) * abs(l2.y - r2.y);
  long long areaI =
      (min(r1.x, r2.x) - max(l1.x, l2.x)) * (min(r1.y, r2.y) - max(l1.y, l2.y));
  return areaI;
}
bool doOverlap(Point l1, Point r1, Point l2, Point r2) {
  if (l1.x > r2.x || l2.x > r1.x) {
    return false;
  }
  if (l1.y > r2.y || l2.y > r1.y) {
    return false;
  }
  return true;
}
Point intersection_botl(Point l1, Point r1, Point l2, Point r2) {
  Point topr, botl;
  topr.y = min(r1.y, r2.y);
  topr.x = min(r1.x, r2.x);
  botl.y = max(l1.y, l2.y);
  botl.x = max(l1.x, l2.x);
  return botl;
}
Point intersection_topr(Point l1, Point r1, Point l2, Point r2) {
  Point topr, botl;
  topr.y = min(r1.y, r2.y);
  topr.x = min(r1.x, r2.x);
  botl.y = max(l1.y, l2.y);
  botl.x = max(l1.x, l2.x);
  return topr;
}
long long comp_two(Point l1, Point l2, Point r1, Point r2) {
  if (doOverlap(l1, r1, l2, r2)) {
    return overlappingArea(l1, r1, l2, r2);
  } else {
    return 0;
  }
}
long long geometric_progression_sum(long long endd, long long st, long long k) {
  return (endd * k - st) / (k - 1);
}
long long geometric_progression_sum_mod(long long endd, long long st,
                                        long long k, long long M) {
  return mul(sub(mul(endd, k, M), st, M), modInverse(k - 1, M), M);
}
long long M = 1e9 + 7;
const int sz = 1e5 + 10;
const int OO = 0x3f3f3f3f;
vector<pair<long long, long long> > v;
bool solve(long long median_val, long long salary, long long n) {
  long long median = (n / 2) + 1;
  for (int i = n - 1; i >= 0; i--) {
    if (v[i].second >= median_val && median > 0) {
      salary -= max(v[i].first, median_val);
      median--;
    } else {
      salary -= v[i].first;
    }
  }
  return (salary >= 0 && median == 0);
}
long long bs(long long l, long long r, long long salary, long long n) {
  long long last = -1;
  while (l <= r) {
    long long mid = l + (r - l) / 2;
    if (solve(mid, salary, n)) {
      l = mid + 1;
      last = mid;
    } else {
      r = mid - 1;
    }
  }
  return last;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  ;
  int t;
  cin >> t;
  while (t--) {
    long long n, s;
    cin >> n >> s;
    v.clear();
    for (int i = 0; i < n; i++) {
      int x, y;
      cin >> x >> y;
      v.push_back({x, y});
    }
    sort(v.begin(), v.end());
    cout << bs(0, 1e18, s, n) << endl;
  }
  return 0;
}
