#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 200005

ll n,s;

struct Node{

    ll l,r;

}p[N];

int cmp(Node a,Node b){

    return a.l<b.l;

}

int judge(ll mid){

    int cnt1=,cnt2=;

    for(int i=;i<=n;i++){

        if(p[i].l>mid)cnt2++;

        if(p[i].r<mid)cnt1++;

    }

    if(cnt1>n/)return ;//偏大了 

    if(1.0*mid*(n/+)>s) return ; 

    ll tot=,cnt=cnt1;

    for(int i=;i<=n;i++){

        if(p[i].l<=mid && p[i].r>=mid){

            ++cnt;

            if(cnt<=n/)

                tot+=p[i].l;

            else if(cnt>=n/+)

                tot+=mid;

        }

        else tot+=p[i].l;

    } 

    if(tot>s)return ;

    return ;

}

int main(){

    int t;cin>>t;

    while(t--){

        cin>>n>>s;

        for(int i=;i<=n;i++)

            scanf("%lld%lld",&p[i].l,&p[i].r);

        sort(p+,p++n,cmp);

        ll L=p[n/+].l,R=s,mid,ans;

        while(L<=R){

            mid=L+R>>;

            if(judge(mid)){

                ans=mid;

                L=mid+;

            }

            else {

                R=mid-;

            }

        }

        cout<<ans<<'\n';

    }

}