#include <bits/stdc++.h>
using namespace std;
const long INF = 1000 * 1000 * 1000;
const long long int mod = 1000000007;
long long int l[300000], r[300000];
int main() {
  std::ios::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    int n, c;
    cin >> n;
    long long int s, sum = 0;
    cin >> s;
    for (int i = 0; i < n; i++) {
      cin >> l[i] >> r[i];
      s -= l[i];
    }
    long long int a = 0, b = INF, ans, mid;
    bool flag = false;
    c = n / 2 + 1;
    while (a <= b) {
      priority_queue<long long int> p;
      flag = false;
      mid = (a + b) / 2;
      sum = 0;
      for (int i = 0; i < n; i++) {
        if (r[i] >= mid) {
          p.push(l[i]);
        }
      }
      if (p.size() >= c) {
        for (int i = 0; i < c; i++) {
          sum += max(0ll, mid - p.top());
          p.pop();
        }
        if (sum <= s) {
          flag = true;
        }
      }
      if (flag) {
        ans = mid;
        a = mid + 1;
      } else {
        b = mid - 1;
      }
    }
    cout << ans << '\n';
  }
}
