CF2140D A Cruel Segment's Thesis

You are given $n$ segments on a number line. The $i$-th segment is represented as $[l_i, r_i]$. Initially, all the segments are unmarked. You perform the following operation repeatedly until there are no unmarked segments left: 1. In the $k$-th operation, if there are at least two unmarked segments, choose any two unmarked segments $[l_i, r_i]$ and $[l_j, r_j]$, mark both of them, and add a new marked segment $[x_k, y_k]$ satisfying the following conditions: - $l_i \leq x_k \leq r_i$, - $l_j \leq y_k \leq r_j$, - $x_k \leq y_k$. 2. If there is exactly one unmarked segment remaining, mark it. Your task is to determine the maximum possible sum of lengths of all the marked segments at the end of the process. Note that the length of a segment $([l,r])$ is $r-l$.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of segments. Each of the next $n$ lines contains two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq 10^9$) — the $i$-th segment. It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

For each test case, print a single integer — the maximum possible total length of all marked segments at the end of the process.

In the first test case, we choose the given two segments and make the new segment $[1, 10^9]$. In the second test case, we choose the segments $[1, 10]$ and $[2, 15]$ and make the new segment $[1,15]$. Now, $[3, 9]$ is the only segment that is left unmarked, and it will be marked in the next step.