#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
int t, n, s;
vector<pii> arr;
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}
bool check(int mid) { // 小的
    vector<bool> vis1(n, 0);
    vector<bool> vis2(n, 0);
    vector<pii> ok;
    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]), vis1[i] = true;
    if (ok.empty()) return false;
    for (int i = 0; i < n; i++)
        if (!vis1[i] && arr[i].first <= mid)
            cnt_s++, vis2[i] = true, sum += arr[i].first;
        else if (!vis1[i] && arr[i].second >= mid)
            cnt_b++, vis2[i] = true, 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;
}