← 返回题目列表

Codeforces · 1251/D

D. 工资变化

中文机器翻译题面 查看原题

您是一家大企业的负责人。 $$$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$$$。