#include <bits/stdc++.h>
    #define nmax 200001

    using namespace std;
    ifstream fin("p.in");
    ofstream fout("p.out");

    const int N = 1e9;

    struct salary{
        long long left,right;
    }vec[nmax];

    int nr;
    long long total;

    bool cmp(salary a,salary b){
        if(a.left == a.right)
            return a.right < b.right;
        return a.left < b.left;
    }

    bool verif(long long val){
        long long sum=0;
        int cnt=0;
        vector<int>v;

        for(int i = 1; i <= nr; i++){
            if(vec[i].right < val)
                sum += vec[i].left;
            else if(vec[i].left >= val){
                sum += vec[i].left;
                cnt++;
            }
            else {
                v.push_back(vec[i].left);
            }
        }

        int ct_v = v.size();
        int need = max(0,((nr + 1)/2 - cnt));

        if(need > ct_v) return 0;
        for(int i = 0; i < ct_v - need; i++)
            sum += v[i];

        for(int i = ct_v - need; i < ct_v; i++)
            sum += val;

        if(sum <= total) return 1;
        return 0;
    }

    int main()
    {
        int t;
        cin>>t;
        for(int j = 1; j <= t; j++){
            cin>>nr>>total;
            for(int i = 1; i <= nr; i++)
                cin>>vec[i].left>>vec[i].right;

            if(nr == 1)
                cout<<min(total,vec[nr].right)<<"\n";
            else{
                sort(vec + 1,vec + nr + 1,cmp);
                long long sol;
                long long st = 0,dr = 1e9;
                while(st <= dr){
                    long long mid = (st + dr)/2;
                    //fout<<mid<<" "<<verif(mid)<<endl;
                    if(verif(mid)){
                        sol = mid;
                        st = mid + 1;
                    }
                    else dr = mid-1;
                }
                //fout<<"next\n";
                cout<<sol<<"\n";
            }
        }

        return 0;
    }