Points Movement
Contest: Codeforces Global Round 16
Difficulty rating: 2600
Tags: data structures, dp, greedy, implementation, sortings

There are $$$n$$$ points and $$$m$$$ segments on the coordinate line. The initial coordinate of the $$$i$$$-th point is $$$a_i$$$. The endpoints of the $$$j$$$-th segment are $$$l_j$$$ and $$$r_j$$$ — left and right endpoints, respectively.

You can move the points. In one move you can move any point from its current coordinate $$$x$$$ to the coordinate $$$x - 1$$$ or the coordinate $$$x + 1$$$. The cost of this move is $$$1$$$.

You should move the points in such a way that each segment is visited by at least one point. A point visits the segment $$$[l, r]$$$ if there is a moment when its coordinate was on the segment $$$[l, r]$$$ (including endpoints).

You should find the minimal possible total cost of all moves such that all segments are visited.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of points and segments respectively.

The next line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the initial coordinates of the points.

Each of the next $$$m$$$ lines contains two integers $$$l_j$$$, $$$r_j$$$ ($$$-10^9 \le l_j \le r_j \le 10^9$$$) — the left and the right endpoints of the $$$j$$$-th segment.

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

Output format:
For each test case print a single integer — the minimal total cost of all moves such that all segments are visited.

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

Note:
In the first test case the points can be moved as follows:

- Move the second point from the coordinate $$$6$$$ to the coordinate $$$5$$$.
- Move the third point from the coordinate $$$14$$$ to the coordinate $$$13$$$.
- Move the fourth point from the coordinate $$$18$$$ to the coordinate $$$17$$$.
- Move the third point from the coordinate $$$13$$$ to the coordinate $$$12$$$.
- Move the fourth point from the coordinate $$$17$$$ to the coordinate $$$16$$$.

The total cost of moves is $$$5$$$. It is easy to see, that all segments are visited by these movements. For example, the tenth segment ($$$[7, 13]$$$) is visited after the second move by the third point.

Here is the image that describes the first test case:

Example input:
2
4 11
2 6 14 18
0 3
4 5
11 15
3 5
10 13
16 16
1 4
8 12
17 19
7 13
14 19
4 12
-9 -16 12 3
-20 -18
-14 -13
-10 -7
-3 -1
0 4
6 11
7 9
8 10
13 15
14 18
16 17
18 19

Example output:
5
22

Editorial:
Firstly, if a point has initially visited some segment, then we can throw it out of consideration. It means that all segments that cover at least one point can be thrown out. This can be done using the binary search for each segment separately.
Secondly, if a segment $$$A$$$ is contained in a segment $$$B$$$ (i.e. $$$l_B \le l_A \le r_A \le r_B$$$), then a point that visited $$$A$$$ will visit $$$B$$$, too. It means that we should save only those segments that do not contain any other segments.
This can be done using a Fenwick tree. Initially, all values in the tree are zeroes. We will consider the segments in decreasing order of $$$l$$$. Let's assume we are considering segment $$$i$$$. If there is an already considered segment $$$j$$$ $$$(r_j \le r_i)$$$, then segment $$$j$$$ is in segment $$$i$$$. It is so because $$$l_i \le l_j$$$ because of the considering order, so $$$l_i \le l_j \le r_j \le r_i$$$. To find the amount of such $$$j$$$ it is enough to find the amount of $$$1$$$ on a prefix until $$$r_i$$$ in the Fenwick tree. Now when we considered the segment $$$i$$$ we set $$$1$$$ in the Fenwick tree on position $$$r_i$$$.
After that there are only segments that do not contain any other segments and they are not initially visited by any point. We will consider only these segments.
Let's say that a segment is assigned to a point if that point visits this segment. Let's find out how to calculate the answer for one point if we already know the set of segments that are assigned to it. Let's consider the segments that are on the left to the point and say that the maximal distance from the point to these segments is $$$a$$$. In the same way let $$$b$$$ be the maximal distance from the point to the segments on the right. Then the answer for the point is $$$2\cdot min(a, b)+max(a, b)$$$.
Now if a segment is between two neighbouring points, then it should be assigned to one of these points. (If a segment is to the left from the leftmost point or to the right from the rightmost point then it should be assigned to the leftmost point or to the rightmost point respectively). Now let's consider the segments between two neighbouring points. These segments are ordered by the left ends and by the right ends at the same time. Some prefix of these segments should be assigned to the left point, other segments (suffix) should be assigned to the right point.
Now let's solve the problem using the dynamic programming. Let $$$dp[i][j]$$$ be the answer if we assigned the segments for first $$$i$$$ points and there are $$$j$$$ segments assigned to the $$$i$$$-th point that are to the right from it. There is a linear amount of dp states. Let's learn to calculate the dp. We will consider the dp states in increasing order of $$$i$$$ and, after that, $$$j$$$. Let $$$b$$$ be the distance from $$$i$$$-th point to $$$j$$$ segment after it. Then $$$dp[i][j]=\displaystyle\min_{0 \le k \le x} \Big(dp[i-1][k]+2\cdot min(b, a_{i, k})+max(b, a_{i, k})\Big)$$$, where $$$a_{i, k}$$$ — is the distance from $$$i$$$-th point to $$$(k+1)$$$-th segment after $$$(i-1)$$$-th point and $$$x$$$ is the amount of segments between points $$$i$$$ and $$$(i+1)$$$. But this is a quadratic dp. Now we can find out that for some prefix of segments after $$$(i-1)$$$-th point $$$a_{i, k}$$$ is greater than $$$b$$$ and for some suffix it is less than $$$b$$$. The length of that prefix may be found using the binary search or two pointers. For $$$k$$$ on that prefix the dp will be $$$dp[i-1][k] + x_i - r_{k+1}+2\cdot b$$$, and for $$$k$$$ on the suffix — $$$dp[i-1][k] + 2\cdot(x_i - r_{k+1})+b$$$. In these formulas everything except $$$b$$$ depends on $$$i$$$ and $$$k$$$. It means that we can calculate dp quickly using prefix and suffix minimums.
The answer is $$$dp[n][x]$$$, where $$$x$$$ is the amount of segments to the right of the rightmost point.