P14786 [NERC 2025] Elevator Against Humanity

如今，所有设备都变得智能：智能手机、智能音箱、智能灯泡，甚至是智能电梯。机器正在崛起。 人类抵抗组织的总部设在一座摩天大楼里。然而，智能电梯试图在不暴露自身的情况下拖慢人们的行动。 摩天大楼里有 $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$。

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

在第一个测试用例中，只有一个人。访问楼层的顺序是 $1 \rightarrow 5 \rightarrow 3$，时间为 $6$。 在第二个测试用例中，一个正确的顺序是 $1 \rightarrow 8 \rightarrow 2 \rightarrow 7 \rightarrow 4$，时间为 $21$。 在第三个测试用例中，一个正确的顺序是 $1 \rightarrow 10 \rightarrow 6 \rightarrow 3 \rightarrow 8$，时间为 $21$。