你是一家大企业的负责人. n个人为你工作, 其中n是奇数 (n不能被2整除).

你必须给你的员工发工资. 最初, 你有s元,第i个员工应该得到的工资范围为从l_i元到r_i元. 你必须以一种方式分配工资, 使中值工资达到可能的最大值.

为了找到一个奇数长度的序列的中值, 你必须对它进行排序,并在排序后取中间位置的元素.

例如: 序列[5,1,10,17,6]的中位数是6,

序列[1,2,1]的中位数为1.

保证你有足够的钱支付最低工资, 即l₁+l₂+⋯⋯+l_n≤s.

注意: 你不必把所有的钱都花在薪水上.

你必须回答t组测试.

第一行1个整数t(1≤t≤2*10⁵), 代表测试用例个数.

第一行分别为2个整数n和s(1≤n<2*10⁵,1≤s≤2*10¹⁴), 分别代表企业雇员人数和奖金. n不能被2整除.

下面n行包含每个员工工资范围信息. 即第i行包含两个整数l_i和r_i(1≤l_i≤r_i≤10⁹).

保证所有n之和不超过2*10⁵.

也保证你有足够的钱支付最低工资给每个员工，即所有的li之和小于等于s 

对于每个测试用例, 打印一个整数——可以获得的最大中值工资.

在第一个测试用例中, 您可以按如下方式分配工资:sal₁=12,sal₂=2,sal₃=11 (sal_i是第i个员工的工资). 那么工资中值是11.

在第二个测试用例中, 您必须向唯一的员工支付1337元.

在第三个测试用例中, 你可以按如下方式分配工资:

sal₁=4,sal₂=3,sal₃=6,sal₄=6,sal₅=7.那么中值工资是6.

朱家琪2021