← 返回题目列表

Codeforces · 2181/E

E. 反人类电梯

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

如今,所有的小工具都是智能的:智能手机、智能音箱、智能灯泡,甚至智能电梯。机器升起。

人类抵抗组织的总部位于一座摩天大楼内。然而,智能电梯试图在不暴露自身的情况下减慢人们的速度。

摩天大楼里有$$$n$$$人在不同楼层等待电梯。每个人都想到达另一层楼。每个人的目的地楼层都不同于其他目的地楼层以及所有起始楼层。一开始,电梯位于一楼。它每单位时间移动一层楼。每当门打开时,它就会选择下一层并直接前往该楼层。电梯既可以到尚未乘电梯的人的起始楼层载人,也可以到已乘电梯的人的目的楼层载人下车。请注意,即使对于已经在电梯内的人来说,电梯也不会停在中间楼层。乘客登机和下机的时间可以忽略不计。电梯足够大,可以同时容纳所有人。

电梯的目标是最大化所有乘客被运送到目的地楼层的总时间。求从一楼开始到最后一位乘客下机的最大总时间。电梯无需返回一楼。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ 表示人数 ($$$1 \le n \le 10^5$$$)。

以下 $$$n$$$ 行中的每一行都包含两个整数 $$$s_i$$$ 和 $$$f_i$$$ ($$$2 \le s_i, f_i \le 10^9$$$) 分别表示该人 $$$i$$$ 的起始楼层和目标楼层。输入中的所有 $$$2n$$$ 楼​​层都是成对不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印运送所有人所需的最长时间。

示例

输入
复制

3
1
5 3
2
2 7
8 4
2
10 8
6 3

输出
复制

6
21
21

注意

第一个测试用例中,只有一个人。访问楼层的顺序为$$$1 \to 5 \to 3$$$,时间为$$$6$$$。

在第二个测试用例中,正确的序列之一是 $$$1 \to 8 \to 2 \to 7 \to 4$$$ ,时间为 $$$21$$$。

在第三个测试用例中,正确的序列之一是 $$$1 \to 10 \to 6 \to 3 \to 8$$$ ,时间为 $$$21$$$。