CF1251D Salary Changing

你是一家大型企业的负责人，有 $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 \times 10^5$），表示测试数据组数。 每组测试数据的第一行包含两个整数 $n$ 和 $s$（$1 \le n < 2 \times 10^5$，$1 \le s \le 2 \times 10^{14}$），分别表示员工人数和你拥有的资金数。$n$ 保证为奇数。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 10^9$），表示第 $i$ 名员工的工资下限和上限。 保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。 同时保证你有足够的钱支付每个人的最低工资，即 $\sum\limits_{i=1}^{n} l_i \le s$。

对于每组测试数据，输出一个整数，表示你能获得的最大中位数工资。

第一组测试数据，你可以这样分配工资：$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$。 由 ChatGPT 4.1 翻译