Jumbo Extra Cheese 2
Contest: Codeforces Round 831 (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: geometry, greedy, sortings

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.

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
4
4 1
4 5
1 1
2 3
3
2 4
2 6
2 3
1
2 65

Example output:
26
24
134

Editorial:
According to the problem, the arrays $$$a$$$ and $$$b$$$ denote the dimensions of the rectangles. Define arrays $$$c$$$ and $$$d$$$ as a certain orientation configuration of the rectangles with $$$c_i$$$ denoting the width and $$$d_i$$$ denoting the height. Define arrays $$$e$$$ and $$$f$$$ as a certain permutation of the orientation configuration such that the $$$i$$$-th rectangle from the left has width $$$e_i$$$ and height $$$f_i$$$.
Consider a certain configuration of $$$e$$$ and $$$f$$$. The perimeter of the connected shape will be $$$2(e_1+e_2+\ldots+e_n)+f_1+|f_1-f_2|+|f_2-f_3|+\ldots+|f_{n-1}-f_n|+f_n$$$.
Notice that if we sort the rectangles based on $$$f_i$$$, the perimeter would become $$$2(e_1+e_2+\ldots+e_n+f_n)$$$. This is actually the minimum possible perimeter for a fixed configuration of $$$c$$$ and $$$d$$$ as we cannot get a smaller perimeter than this. This means, if we have a certain configuration of $$$c$$$ and $$$d$$$, the optimal perimeter is $$$2(c_1+c_2+\ldots+c_n+\max(d))$$$. Now, we just need to find a configuration of $$$c$$$ and $$$d$$$ from $$$a$$$ and $$$b$$$ that results in the minimum value of $$$2(c_1+c_2+\ldots+c_n+\max(d))$$$.
Notice that each element of $$$a$$$ and $$$b$$$ can only be counted either $$$0$$$ or $$$2$$$ times in the final answer. Consider the maximum value out of all elements of $$$a$$$ and $$$b$$$. If there are multiple values that are maximum, just consider one of them. We can see that that value will always be counted $$$2$$$ times no matter how we construct $$$c$$$ and $$$d$$$.
We need to determine whether to put that maximum value in $$$c$$$ (width) or $$$d$$$ (height). It is actually better to put that value in $$$d$$$ as it will cause all other values of $$$d$$$ to be counted $$$0$$$ times in the final answer.
Now, we just need to determine the orientation for each of the other rectangles. We have determined that the maximum value in $$$a$$$ and $$$b$$$ must be put in $$$d$$$, which will automatically become the value of $$$\max(d)$$$. Therefore, all other values in $$$d$$$ will be counted $$$0$$$ times in the final answer. This means, because we want to minimise the final answer, for each $$$i$$$, it is always better to put the larger value out of $$$a_i$$$ and $$$b_i$$$ in $$$d$$$ as it will cause the value that is not being counted in the final answer to be larger.
Using every observation above, in order to get the minimum possible perimeter, we can do the following:
1. Construct the arrays $$$c$$$ and $$$d$$$ with $$$c_i$$$ and $$$d_i$$$ taking their values from $$$a_i$$$ and $$$b_i$$$ while making $$$c_i\leq d_i$$$.
2. The answer is $$$2(c_1+c_2+\ldots+c_n+\max(d))$$$.
Time complexity for each test case: $$$O(n)$$$