题目描述

对于一个长度为奇数的数列，我们称它的 中位数 为数列中所有元素从小到大排序后中间的那个数。比如：

• 数列 $\{5\}$ 的中位数是 $5$；
• 数列 $\{1, 3, 5\}$ 的中位数是 $3$；
• 数列 $\{1, 2, 2, 7, 9\}$ 的中位数是 $2$；
• 数列 $\{3, 5, 8, 9, 9, 11, 12\}$ 的中位数是 $9$。

现在给你两个整数 $n$ 和 $s$（$1 \le n \lt 2 \cdot 10^5$ 且 $n$ 为奇数，$1 \le s \le 2 \cdot 10^{14}$）。

你需要构造一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，要求所有元素之和不超过 $s$（即 $\sum\limits_{i=1}^n {a_i} \le s$），且要求对于任意 $1 \le i \le n$，均有 $l_i \le a_i \le r_i$ 成立。

在此条件下你希望数列 $a$ 的中位数最大。

求：能够构造的满足条件的数列的中位数的最大值。

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $t(1 \le t \le 1000)$，表示测试数据组数。

每组测试数据的第一行包含两个整数 $n$ 和 $s$（$1 \le n \le 2 \cdot 10^5, 1 \le s \le 2 \cdot 10^{14}$）。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 10^9$）。

数据保证：

• 所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$
• 每组测试数据的 $\sum\limits_{i=1}^n {l_i} \le s$（即没组测试数据都存在合法的解）

输出格式

对于每组测试数据，输出一行，包含一个整数，表示能够得到的最大的满足条件的中位数。

3
3 26
10 12
1 4
10 11
1 1337
1 1000000000
5 26
4 4
2 4
6 8
5 6
2 7

11
1337
6

说明/提示

样例解释

第一组测试数据：$a = \{ 12, 2, 11 \}$，中位数为 $11$
第二组测试数据：$a = \{ 1337 \}$，中位数为 $1337$
第三组测试数据：$a = \{ 4,3,6,6,7 \}$，中位数为 $6$

数据规模与约定

• 对于 $30\%$ 的测试数据，$t \le 10, n \lt 20, r_i \le 100, s \le 2000$；
• 对于 $60\%$ 的测试数据，$t \le 100, n \lt 2000, r_i \le 10^6, s \le 2 \cdot 10^9$；
• 对于 $100\%$ 的测试数据，$1 \le t \le 1000, 1 \le n \lt 2 \cdot 10^5$ 且 $n$ 为奇数, $1 \le l_i \le r_i \le 10^9, \sum\limits_{i=1}^n {a_i} \le s \le 2 \cdot 10^{14}$，且所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$.