#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
int t, n, s;
vector<pii> ok;
vector<pii> arr;
bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}
bool check(int mid) {
    ok.clear();
    int cnt_s = 0, cnt_b = 0, sum = 0;
    for (int i = 0; i < n; i++)
        if (arr[i].first <= mid && mid <= arr[i].second)
            ok.push_back(arr[i]);
        else if (arr[i].second < mid)
            cnt_s++, sum += arr[i].first;
        else if (arr[i].first > mid)
            cnt_b++, sum += arr[i].first;
    if (cnt_s > n / 2) return false;
    if (cnt_b > n / 2) return false;
    cnt_s = n / 2 - cnt_s, cnt_b = n / 2 - cnt_b;
    for (int i = 0; i < cnt_s; i++) sum += arr[i].first;
    for (int i = cnt_s; i < ok.size(); i++) sum += mid;
    return sum <= s;
}
int binary_search() {
    int ans, l = 1, r = 200000000;
    while (l <= r) {
        int mid = (l + r) >> 1ll;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}
signed main() {
    cin >> t;
    while (t--) {
        cin >> n >> s;
        arr.resize(n);
        for (pair<int, int>& i : arr) cin >> i.first >> i.second;
        sort(arr.begin(), arr.end(), cmp);
        cout << binary_search() << '\n';
    }
    return 0;
}