#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
	int lt, rt;
}a[200005];
bool cmp(node x, node y)
{
	return x.lt<y.lt;
}
int t, n, s, alt;
int tem[200005], id;
bool check(int x)
{
	id=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i].rt>=x)
		{
			tem[++id]=max(x-a[i].lt,0ll);
		}
	}
	sort(tem+1,tem+1+id);
	if(id<n/2+1)return 0;
	int cnt=0;
	for(int i=1;i<=n/2+1;i++)
	{
		cnt+=tem[i];
	}
	return cnt<=s-alt;
}
signed main()
{
	for(cin>>t;t;t--)
	{
		cin>>n>>s;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].lt>>a[i].rt;
			alt+=a[i].lt;
		}
//		sort(a+1,a+1+n,cmp);
		int lt=0,rt=1e18+1;
		while(lt+1<rt)
		{
			int mid=lt+rt>>1;
			if(check(mid))
			{
				lt=mid;
			}
			else rt=mid;
		}
		cout<<lt<<"\n";
	}
}