CF2181E.Elevator Against Humanity

Nowadays, all gadgets are smart: smart phones, smart speakers, smart bulbs, and even smart elevators. The machines rise up.

The headquarters of the human resistance is located in a skyscraper. However, the smart elevator tries to slow people down without revealing itself.

There are $n$ people in the skyscraper waiting for the elevator on different floors. Each person wants to get to another floor. Each person's destination floor is different from every other destination floor and from all starting floors. At the beginning, the elevator is located on the first floor. It moves one floor per unit of time. Whenever the doors open, it chooses the next floor and travels directly to it. The elevator can either go to the starting floor of the person who hasn't boarded the elevator yet and take them, or go to the destination floor of the person who is already in the elevator and disembark them. Note that the elevator doesn't stop on the intermediate floors even for the people who are already inside the elevator. The passenger boarding and disembarkation take negligible time. The elevator is big enough to accommodate all people at the same time.

The goal of the elevator is to maximize the total time until all passengers have been delivered to their destination floors. Find the maximum total time starting from the first floor until the disembarkation of the last passenger. Elevator doesn't need to return to the first floor.

如今，所有电子设备都变得“智能”：智能手机、智能音箱、智能灯泡，甚至智能电梯。机器正在崛起。

人类抵抗组织的总部位于一座摩天大楼中。然而，这座智能电梯试图在不暴露自身意图的情况下延缓人员通行。

摩天大楼中有 $n$ 个人，分别在不同楼层等待电梯。每个人均需前往另一个楼层，且所有人的目标楼层互不相同，并且与所有起始楼层也互不相同。初始时刻，电梯位于第 1 层。电梯每单位时间移动一层楼。每次电梯门开启时，它选择下一个目标楼层并直接驶向该层（途中不停靠）。电梯有两种可选操作：

• 前往某位尚未上电梯人员的起始楼层，将其接上；
• 前往某位已在电梯内人员的目标楼层，将其送下。

注意：电梯在前往目标楼层途中，即使有乘客已在电梯内且其目标楼层位于路径上，也不会中途停靠。乘客上下电梯所需时间为零。电梯容量足够大，可同时容纳所有人。

电梯的目标是最大化所有乘客全部抵达各自目标楼层所需的总时间。请计算从电梯初始位于第 1 层开始，直到最后一名乘客被送达目标楼层为止的最大可能总时间。电梯无需在任务结束后返回第 1 层。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ denoting the number of people ($1 \le n \le 10^5$).

Each of the following $n$ lines contains two integers $s_i$ and $f_i$ ($2 \le s_i, f_i \le 10^9$) denoting the starting and the destination floor of the person $i$, respectively. All $2n$ floors in the input are pairwise distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print the maximum time needed to transport all people.

对于每个测试用例，输出运送所有人所需的最长时间。

In the first test case, there is only one person. The sequence of visited floors is $1 \to 5 \to 3$, and the time is $6$.

In the second test case, one of the correct sequences is $1 \to 8 \to 2 \to 7 \to 4$ with the time $21$.

In the third test case, one of the correct sequences is $1 \to 10 \to 6 \to 3 \to 8$ with the time $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$。