您是一家大企业的负责人。 $$$n$$$ 的人为你工作,而 $$$n$$$ 是奇数(即 $$$n$$$ 不能被 $$$2$$$ 整除)。
您必须向员工分配工资。最初,您有 $$$s$$$ 美元,第 $$$i$$$ 员工的工资应为 $$$l_i$$$ 到 $$$r_i$$$ 美元。你必须以工资中位数尽可能最大的方式分配工资。
要找到奇数长度的序列的中位数,您必须对其进行排序,并在排序后取出中间位置的元素。例如:
- 序列 $$$[5, 1, 10, 17, 6]$$$ 的中位数是 $$$6$$$,
- 序列 $$$[1, 2, 1]$$$ 的中位数是 $$$1$$$。
保证您有足够的钱支付最低工资,即$$$l_1 + l_2 + \dots + l_n \le s$$$。
请注意,您不必将所有 $$$s$$$ 美元花在工资上。
您必须回答 $$$t$$$ 测试用例。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。
每个查询的第一行包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \le n < 2 \cdot 10^5$$$, $$$1 \le s \le 2 \cdot 10^{14}$$$) — 员工数量和您拥有的金额。值 $$$n$$$ 不能被 $$$2$$$ 整除。
每个查询的以下 $$$n$$$ 行包含有关员工的信息。第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$)。
保证所有查询的所有 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。
还保证您有足够的钱支付每个员工的最低工资,即。 e. $$$\sum\limits_{i=1}^{n} l_i \le s$$$。
输出
对于每个测试用例,打印一个整数 - 您可以获得的最高中位数工资。
示例
输入 #1
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
输出 #1
11 1337 6
注意
在第一个测试用例中,您可以按如下方式分配工资:$$$sal_1 = 12, sal_2 = 2, sal_3 = 11$$$($$$sal_i$$$ 是第 $$$i$$$ 员工的工资)。那么工资中位数是$$$11$$$。
在第二个测试用例中,您必须向唯一的员工支付 $$$1337$$$ 美元。
在第三个测试用例中,您可以按如下方式分配工资:$$$sal_1 = 4, sal_2 = 3, sal_3 = 6, sal_4 = 6, sal_5 = 7$$$。那么工资中位数是$$$6$$$。