CF1740B.Jumbo Extra Cheese 2

Pak Chanek has $n$ two-dimensional slices of cheese. The $i$-th slice of cheese can be represented as a rectangle of dimensions $a_i \times b_i$. We want to arrange them on the two-dimensional plane such that:

• Each edge of each cheese is parallel to either the x-axis or the y-axis.
• The bottom edge of each cheese is a segment of the x-axis.
• No two slices of cheese overlap, but their sides can touch.
• They form one connected shape.

Note that we can arrange them in any order (the leftmost slice of cheese is not necessarily the first slice of cheese). Also note that we can rotate each slice of cheese in any way as long as all conditions still hold.

Find the minimum possible perimeter of the constructed shape.

帕克·查内克有 $n$ 片二维奶酪。第 $i$ 片奶酪可表示为一个 $a_i \times b_i$ 的矩形。我们希望将它们放置在二维平面上，满足以下条件：

• 每片奶酪的每条边均平行于 $x$ 轴或 $y$ 轴；
• 每片奶酪的底边均位于 $x$ 轴上（即是一段 $x$ 轴上的线段）；
• 任意两片奶酪互不重叠（但允许边相接）；
• 所有奶酪构成一个连通图形。

注意：我们可以以任意顺序排列这些奶酪（最左侧的奶酪不一定是第 $1$ 片奶酪）。此外，每片奶酪均可任意旋转（即交换其长宽），只要所有上述条件仍被满足即可。

求所构造图形的最小可能周长。

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of slices of cheese Pak Chanek has.

The $i$-th of the next $n$ lines of each test case contains two integers $a_i$ and $b_i$ ($1 \leq a_i,b_i \leq 10^9$) — the dimensions of the $i$-th slice of cheese.

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 2 \cdot 10^4$），表示测试用例的数量。接下来的各行描述各个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示 Pak Chanek 拥有的奶酪片数量。

每个测试用例接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i,b_i \leq 10^9$），分别表示第 $i$ 片奶酪的尺寸。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output a line containing an integer representing the minimum possible perimeter of the constructed shape.

对于每个测试用例，输出一行，包含一个整数，表示所构造图形的最小可能周长。

In the first test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.

We can calculate that the perimeter of the constructed shape is $2+5+1+1+1+1+3+1+5+1+2+3=26$. It can be shown that we cannot get a smaller perimeter.

Consider the following invalid arrangement.

Even though the perimeter of the shape above is $24$, it does not satisfy all conditions of the problem. The bottom edge of the $1 \times 1$ slice of cheese is not a segment of the x-axis.

In the second test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.

We can calculate that the perimeter of the constructed shape is $2+2+2+3+2+3+2+2+2+4=24$. It can be shown that we cannot get a smaller perimeter.

在第一个测试用例中，一种得到最小可能周长的奶酪片摆放方式如下所示。

我们可以计算出所构造图形的周长为 $2+5+1+1+1+1+3+1+5+1+2+3=26$。可以证明，无法得到更小的周长。

考虑以下不合法的摆放方式：

尽管上述图形的周长为 $24$，但它并不满足题目的全部条件：$1 \times 1$ 奶酪片的底边并非 $x$ 轴上的一段线段。

在第二个测试用例中，一种得到最小可能周长的奶酪片摆放方式如下所示。

我们可以计算出所构造图形的周长为 $2+2+2+3+2+3+2+2+2+4=24$。可以证明，无法得到更小的周长。