#include <bits/stdc++.h>
using namespace std;
long long n, s, INI;
pair<long long, long long> a[200010];
bool op(long long meta) {
  long long quant = 0, disponivel = s;
  for (long long i = n; i >= 1; i--) {
    long long vez = meta - a[i].first;
    if (a[i].first >= meta) {
      quant++;
      continue;
    }
    if (a[i].second < meta) continue;
    if (vez > disponivel) continue;
    disponivel -= vez;
    quant++;
  }
  long long precisa = n / 2;
  precisa++;
  if (quant >= precisa)
    return true;
  else
    return false;
}
void solve() {
  cin >> n >> INI;
  for (long long i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
  sort(a + 1, a + n + 1);
  s = INI;
  for (long long i = 1; i <= n; i++) s -= a[i].first;
  long long ini = 1, fim = 200000000000000;
  while (ini <= fim) {
    long long meio = (ini + fim) / 2;
    if (op(meio)) {
      bool prox = op(meio + 1);
      if (!prox) {
        cout << meio << "\n";
        return;
      }
      ini = meio + 1;
    } else {
      bool ant = op(meio - 1);
      if (ant) {
        cout << meio - 1 << "\n";
        return;
      }
      fim = meio - 1;
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long t;
  cin >> t;
  for (long long i = 1; i <= t; i++) solve();
}
