import std.stdio;
import std.algorithm;
import std.typecons : tuple, Tuple;
import std.container.rbtree;

int n;
long s;
int[] l;
int[] r;


bool can(long m) {
	int cnt = 0;
	int other = n;
	long sum = 0;
	for(int i = 0; i < n; ++i) {
		if (m < l[i]) {
			++cnt;
			sum += l[i];
			--other;
		} else if (r[i] < m) {
			sum += l[i];
			--other;
		}
	}
	if (cnt + other < (n + 1) / 2) {
		return false;
	}
	int[] ls = new int[other];
	int ptr = 0;
	for(int i = 0; i < n; ++i) {
		if (l[i] <= m && m <= r[i]) {
			ls[ptr] = l[i];
			++ptr;
		}
	}
	sort(ls);
	for(int i = other - 1; i >= 0; --i) {
		if (i >= other - ((n+1)/2 - cnt)) {
			sum += m;
		} else {
			sum += ls[i];
		}
	}
	return sum <= s;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t --> 0) {
		scanf("%d%lld", &n, &s);
		l = new int[n];
		r = new int[n];
		for(int i = 0; i < n; ++i) {
			scanf("%d%d", &l[i], &r[i]);
		}
		long tl = 0, tr = s + 1;
		while (tl+1 < tr) {
			long tm = (tl+tr) / 2;
			if (can(tm)) {
				tl = tm;
			} else {
				tr = tm;
			}
		}
		printf("%lld\n", tl);
	}
	
	return 0;
}