Absolute Cinema

Key Observation

For each index $i$, after optionally swapping, exactly one of the two numbers goes into $a_i$, and the other goes into $b_i$.

Let $c_i$ be the value chosen for $a_i$. Then the value placed in $b_i$ is $a_i+b_i-c_i$. The objective is

$$\max_i c_i+\sum_{i=1}^{n}(a_i+b_i-c_i).$$

The pair sums are fixed, so this is

$$\sum_{i=1}^{n}(a_i+b_i)-\left(\sum_{i=1}^{n}c_i-\max_i c_i\right).$$

The first term is constant. Therefore, maximizing the answer is the same as minimizing

$$\sum_{i=1}^{n}c_i-\max_i c_i.$$

That expression is just the sum of all chosen $a$-values except the largest one. One chosen value gets ignored. That is the whole trick.

Lower Bound

Define

$$m_i=\min(a_i,b_i), \qquad M=\max_{i=1}^{n}m_i, \qquad S=\sum_{i=1}^{n}m_i.$$

No matter what we choose, we always have

$$c_i\ge m_i.$$

Suppose the maximum chosen $c_i$ occurs at index $k$. Then

$$\sum_{i=1}^{n}c_i-\max_i c_i =\sum_{i\ne k}c_i \ge \sum_{i\ne k}m_i =S-m_k \ge S-M.$$

So the penalty can never be smaller than $S-M$.

Achievability

Now choose

$$c_i=m_i=\min(a_i,b_i)$$

for every index. In plain English: put the smaller number of each pair into $a$, and the larger number into $b$.

Then

$$\max_i c_i=M,$$

and

$$\sum c_i-\max c_i=S-M.$$

This exactly matches the lower bound, so it is optimal. No need for some fake complicated greedy. The best greedy is just “smaller upstairs, bigger downstairs.”

Therefore the answer is

$$\boxed{\sum_{i=1}^{n}\max(a_i,b_i)+\max_{i=1}^{n}\min(a_i,b_i)}.$$

Complexity

We scan the arrays once per test case.

$$O(n) \text{ time per test case}, \qquad O(n) \text{ memory}$$

The memory can be $O(1)$ beyond storing one array, but storing $a$ is already perfectly fine for $\sum n\le 10^5$. Use long long, because the answer can be around $10^{14}$.